<!DOCTYPE HTML>
<html lang="zh-CN">


<head>
    <meta charset="utf-8">
    <meta name="keywords" content="A*算法-Python实现, python,machine learning,deep learning,html,css,c,c++,cpp,cmake,ros,linux,ubuntu">
    <meta name="description" content="本文主要提供了Python版本的A*路径规划算法实现，并在此基础上提供了命令行和基于Matplotlib的GUI用户界面（User Interface）">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=no">
    <meta name="renderer" content="webkit|ie-stand|ie-comp">
    <meta name="mobile-web-app-capable" content="yes">
    <meta name="format-detection" content="telephone=no">
    <meta name="apple-mobile-web-app-capable" content="yes">
    <meta name="apple-mobile-web-app-status-bar-style" content="black-translucent">
    <meta name="referrer" content="no-referrer-when-downgrade">
    <!-- Global site tag (gtag.js) - Google Analytics -->


    <title>A*算法-Python实现 | JackWang&#39;s Blog</title>
    <link rel="icon" type="image/png" href="/favicon.png">

    <link rel="stylesheet" type="text/css" href="/libs/awesome/css/all.min.css">
    <link rel="stylesheet" type="text/css" href="/libs/materialize/materialize.min.css">
    <link rel="stylesheet" type="text/css" href="/libs/aos/aos.css">
    <link rel="stylesheet" type="text/css" href="/libs/animate/animate.min.css">
    <link rel="stylesheet" type="text/css" href="/libs/lightGallery/css/lightgallery.min.css">
    <link rel="stylesheet" type="text/css" href="/css/matery.css">
    <link rel="stylesheet" type="text/css" href="/css/my.css">

    <script src="/libs/jquery/jquery-3.6.0.min.js"></script>

<meta name="generator" content="Hexo 5.4.2">
<style>.github-emoji { position: relative; display: inline-block; width: 1.2em; min-height: 1.2em; overflow: hidden; vertical-align: top; color: transparent; }  .github-emoji > span { position: relative; z-index: 10; }  .github-emoji img, .github-emoji .fancybox { margin: 0 !important; padding: 0 !important; border: none !important; outline: none !important; text-decoration: none !important; user-select: none !important; cursor: auto !important; }  .github-emoji img { height: 1.2em !important; width: 1.2em !important; position: absolute !important; left: 50% !important; top: 50% !important; transform: translate(-50%, -50%) !important; user-select: none !important; cursor: auto !important; } .github-emoji-fallback { color: inherit; } .github-emoji-fallback img { opacity: 0 !important; }</style>
<link rel="stylesheet" href="/css/prism-tomorrow.css" type="text/css">
<link rel="stylesheet" href="/css/prism-line-numbers.css" type="text/css"></head>



   <style>
    body{
       background-image: url(https://cdn.jsdelivr.net/gh/Tokisaki-Galaxy/res/site/medias/background.jpg);
       background-repeat:no-repeat;
       background-size: 100% 100%;
       background-attachment:fixed;
    }
</style>



<body>
    <header class="navbar-fixed">
    <nav id="headNav" class="bg-color nav-transparent">
        <div id="navContainer" class="nav-wrapper container">
            <div class="brand-logo">
                <a href="/" class="waves-effect waves-light">
                    
                    <img src="/medias/logo.png" class="logo-img" alt="LOGO">
                    
                    <span class="logo-span">JackWang&#39;s Blog</span>
                </a>
            </div>
            

<a href="#" data-target="mobile-nav" class="sidenav-trigger button-collapse"><i class="fas fa-bars"></i></a>
<ul class="right nav-menu">
  
  <li class="hide-on-med-and-down nav-item">
    
    <a href="/" class="waves-effect waves-light">
      
      <i class="fas fa-home" style="zoom: 0.6;"></i>
      
      <span>首页</span>
    </a>
    
  </li>
  
  <li class="hide-on-med-and-down nav-item">
    
    <a href="" class="waves-effect waves-light">

      
      <i class="fas fa-book-reader" style="zoom: 0.6;"></i>
      
      <span>博客</span>
      <i class="fas fa-chevron-down" aria-hidden="true" style="zoom: 0.6;"></i>
    </a>
    <ul class="sub-nav menus_item_child ">
      
      <li>
        <a href="/tags">
          
          <i class="fas fa-tags" style="margin-top: -20px; zoom: 0.6;"></i>
          
	  <span>按标签归类文章</span>
        </a>
      </li>
      
      <li>
        <a href="/categories">
          
          <i class="fas fa-bookmark" style="margin-top: -20px; zoom: 0.6;"></i>
          
	  <span>按目录归类文章</span>
        </a>
      </li>
      
      <li>
        <a href="/archives">
          
          <i class="fas fa-archive" style="margin-top: -20px; zoom: 0.6;"></i>
          
	  <span>按日期分类文章</span>
        </a>
      </li>
      
    </ul>
    
  </li>
  
  <li class="hide-on-med-and-down nav-item">
    
    <a href="/about" class="waves-effect waves-light">
      
      <i class="fas fa-user-circle" style="zoom: 0.6;"></i>
      
      <span>关于</span>
    </a>
    
  </li>
  
  <li>
    <a href="#searchModal" class="modal-trigger waves-effect waves-light">
      <i id="searchIcon" class="fas fa-search" title="搜索" style="zoom: 0.85;"></i>
    </a>
  </li>
</ul>



<div id="mobile-nav" class="side-nav sidenav">

    <div class="mobile-head bg-color">
        
        <img src="/medias/logo.png" class="logo-img circle responsive-img">
        
        <div class="logo-name">JackWang&#39;s Blog</div>
        <div class="logo-desc">
            
            JackWang的个人博客
            
        </div>
    </div>

    <ul class="menu-list mobile-menu-list">
        
        <li class="m-nav-item">
	  
		<a href="/" class="waves-effect waves-light">
			
			    <i class="fa-fw fas fa-home"></i>
			
			首页
		</a>
          
        </li>
        
        <li class="m-nav-item">
	  
		<a href="javascript:;">
			
				<i class="fa-fw fas fa-book-reader"></i>
			
			博客
			<span class="m-icon"><i class="fas fa-chevron-right"></i></span>
		</a>
            <ul  style="background:  ;" >
              
                <li>

                  <a href="/tags " style="margin-left:75px">
				  
				   <i class="fa fas fa-tags" style="position: absolute;left:50px" ></i>
			      
                              <span>按标签归类文章</    span>

                  </a>
                </li>
              
                <li>

                  <a href="/categories " style="margin-left:75px">
				  
				   <i class="fa fas fa-bookmark" style="position: absolute;left:50px" ></i>
			      
                              <span>按目录归类文章</    span>

                  </a>
                </li>
              
                <li>

                  <a href="/archives " style="margin-left:75px">
				  
				   <i class="fa fas fa-archive" style="position: absolute;left:50px" ></i>
			      
                              <span>按日期分类文章</    span>

                  </a>
                </li>
              
            </ul>
          
        </li>
        
        <li class="m-nav-item">
	  
		<a href="/about" class="waves-effect waves-light">
			
			    <i class="fa-fw fas fa-user-circle"></i>
			
			关于
		</a>
          
        </li>
        
        
    </ul>
</div>


        </div>

        
    </nav>

</header>

    
<script src="/libs/cryptojs/crypto-js.min.js"></script>
<script>
    (function() {
        let pwd = '';
        if (pwd && pwd.length > 0) {
            if (pwd !== CryptoJS.SHA256(prompt('抱歉，这篇文章并不想让所有人都看到，请输入授权密码观看')).toString(CryptoJS.enc.Hex)) {
                alert('密码错误，将返回主页！');
                location.href = '/';
            }
        }
    })();
</script>




<div class="bg-cover pd-header post-cover" style="background-image: url('https://jack-1307599355.cos.ap-shanghai.myqcloud.com/img/a_star.gif')">
    <div class="container" style="right: 0px;left: 0px;">
        <div class="row">
            <div class="col s12 m12 l12">
                <div class="brand">
                    <h1 class="description center-align post-title">A*算法-Python实现</h1>
                </div>
            </div>
        </div>
    </div>
</div>




<main class="post-container content">

    
    <link rel="stylesheet" href="/libs/tocbot/tocbot.css">
<style>
    #articleContent h1::before,
    #articleContent h2::before,
    #articleContent h3::before,
    #articleContent h4::before,
    #articleContent h5::before,
    #articleContent h6::before {
        display: block;
        content: " ";
        height: 100px;
        margin-top: -100px;
        visibility: hidden;
    }

    #articleContent :focus {
        outline: none;
    }

    .toc-fixed {
        position: fixed;
        top: 64px;
    }

    .toc-widget {
        width: 345px;
        padding-left: 20px;
    }

    .toc-widget .toc-title {
        padding: 35px 0 15px 17px;
        font-size: 1.5rem;
        font-weight: bold;
        line-height: 1.5rem;
    }

    .toc-widget ol {
        padding: 0;
        list-style: none;
    }

    #toc-content {
        padding-bottom: 30px;
        overflow: auto;
    }

    #toc-content ol {
        padding-left: 10px;
    }

    #toc-content ol li {
        padding-left: 10px;
    }

    #toc-content .toc-link:hover {
        color: #42b983;
        font-weight: 700;
        text-decoration: underline;
    }

    #toc-content .toc-link::before {
        background-color: transparent;
        max-height: 25px;

        position: absolute;
        right: 23.5vw;
        display: block;
    }

    #toc-content .is-active-link {
        color: #42b983;
    }

    #floating-toc-btn {
        position: fixed;
        right: 15px;
        bottom: 76px;
        padding-top: 15px;
        margin-bottom: 0;
        z-index: 998;
    }

    #floating-toc-btn .btn-floating {
        width: 48px;
        height: 48px;
    }

    #floating-toc-btn .btn-floating i {
        line-height: 48px;
        font-size: 1.4rem;
    }
</style>
<div class="row">
    <div id="main-content" class="col s12 m12 l9">
        <!-- 文章内容详情 -->
<div id="artDetail">
    <div class="card">
        <div class="card-content article-info">
            <div class="row tag-cate">
                <div class="col s7">
                    
                    <div class="article-tag">
                        
                            <a href="/tags/DataStructure/">
                                <span class="chip bg-color">DataStructure</span>
                            </a>
                        
                            <a href="/tags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/">
                                <span class="chip bg-color">数据结构</span>
                            </a>
                        
                            <a href="/tags/A/">
                                <span class="chip bg-color">A*</span>
                            </a>
                        
                            <a href="/tags/PathPlanning/">
                                <span class="chip bg-color">PathPlanning</span>
                            </a>
                        
                            <a href="/tags/Python/">
                                <span class="chip bg-color">Python</span>
                            </a>
                        
                            <a href="/tags/Matplotlib/">
                                <span class="chip bg-color">Matplotlib</span>
                            </a>
                        
                            <a href="/tags/GUI/">
                                <span class="chip bg-color">GUI</span>
                            </a>
                        
                    </div>
                    
                </div>
                <div class="col s5 right-align">
                    
                    <div class="post-cate">
                        <i class="fas fa-bookmark fa-fw icon-category"></i>
                        
                            <a href="/categories/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/" class="post-category">
                                数据结构与算法
                            </a>
                        
                    </div>
                    
                </div>
            </div>

            <div class="post-info">
                
                <div class="post-date info-break-policy">
                    <i class="far fa-calendar-minus fa-fw"></i>发布日期:&nbsp;&nbsp;
                    2021-12-22
                </div>
                

                
                <div class="post-date info-break-policy">
                    <i class="far fa-calendar-check fa-fw"></i>更新日期:&nbsp;&nbsp;
                    2023-06-01
                </div>
                

                
                <div class="info-break-policy">
                    <i class="far fa-file-word fa-fw"></i>文章字数:&nbsp;&nbsp;
                    5.9k
                </div>
                

                
                <div class="info-break-policy">
                    <i class="far fa-clock fa-fw"></i>阅读时长:&nbsp;&nbsp;
                    27 分
                </div>
                

                
                    <div id="busuanzi_container_page_pv" class="info-break-policy">
                        <i class="far fa-eye fa-fw"></i>阅读次数:&nbsp;&nbsp;
                        <span id="busuanzi_value_page_pv"></span>
                    </div>
				
            </div>
        </div>
        <hr class="clearfix">

        

        

        <div class="card-content article-card-content">
            <div id="articleContent">
                <blockquote>
<p>本文主要提供了Python版本的A*路径规划算法实现，并在此基础上提供了命令行和基于Matplotlib的GUI用户界面（User Interface）</p>
</blockquote>
<p><img src="https://jack-1307599355.cos.ap-shanghai.myqcloud.com/img/a_star.gif" alt="完整效果"></p>
<h1 id="A-算法-Python实现"><a href="#A-算法-Python实现" class="headerlink" title="A*算法-Python实现"></a>A*算法-Python实现</h1><p>路径规划算法是计算机届中非常重要的算法，在不少领域都能够看到路径规划算法的应用，最直接的应用例如打车软件为你规划出路径、迷宫问题的求解等等；而复杂一些的、不直接的应用如六自由度机械臂在空间中运动轨迹的规划可以看做是在六维空间的路径规划、火星车在火星表面的探索等等都可以视为路径规划问题，从而使用路径规划算法进行求解。</p>
<p>路径规划算法大体上可以分为两类：<strong>静态路径规划</strong>以及<strong>动态路径规划</strong>。所谓静态静态路径规划指的是提前已知全局地图的前提下进行路径规划；而动态路径规划则指的是预先并不知道全局地图或者仅知道全局地图的一部分，在此基础上对全局地图进行探索的同时动态的利用获取到的信息指导路径规划，最终达到终点。在我们的认知上，一般当然是动态路径规划算法会好很多，因为我们往往并不知道全局地图，而且对于我们人类来说，在一个陌生环境下进行路径规划、到达终点更是我们所希望的。然而在现实中在一些场景中确实全局地图是可以提前获得的，因此针对这些场景，开发出来资源占用更少、速度更快、路径更优的算法就还是有必要的。</p>
<p>其实动态路径规划更进一步，在探索的构建出来全局地图，那就成了SLAM问题了，即同时定位与建图（Simultaneous Localization And Mapping，SLAM）。关于SLAM本文就不再深入了。</p>
<p>本文将要介绍的A<em>算法就是属于静态路径规划算法的其中一种。在诸多的静态路径规划算法里，A\</em>算法可以和暴力搜索（广度优先、深度优先）一样，获得最优的路径，并且资源消耗远远小于广度优先和深度优先。因此有广泛的应用。</p>
<p>本文将在介绍A*算法的基础上提供一种A*算法的Python实现，并在此基础上讲解实现的代码</p>
<h2 id="0-前言"><a href="#0-前言" class="headerlink" title="0. 前言"></a>0. 前言</h2><p>其实我现在是一个大二的计算机系学生，最近数据结构课程的配套实验要求学生从十四个题中选择四个来做。本篇博客就是对应的迷宫问题的求解代码。求解问题比较简单，但是这样就太没有意思了，所以在实现文本字符的迷宫求解基础上，我想为自己带来一些挑战，增加一些趣味性与难度。</p>
<p>因此在基础的求解迷宫问题的要求上，我利用Matplotlib中的Interactive Plotting Method将路径规划的过程以GUI的形式表达出来，并在此基础上提供地图绘制、地图保存等一系列功能，最后完成一个不错的程序。</p>
<p><img src="https://jack-1307599355.cos.ap-shanghai.myqcloud.com/img/image-20211221220005902.png" alt="数据结构算法实验"></p>
<h2 id="1-A-算法"><a href="#1-A-算法" class="headerlink" title="1. A*算法"></a>1. A*算法</h2><p>其实关于A<em>算法并没有什么好说的，网上不少博客对A\</em>算法都有了非常深入的介绍，因此我这里就不在赘述了，避免班门弄斧。</p>
<p>而对于A*算法，需要理解的关键之处就是在启发值的运用。启发值描述了当前点到终点的估计距离，因此相比于深度有限和广度优先，A*算法每次都会去寻找离终点距离比较近的点作为下一个点，从而避免了漫无目的、低效率的遍历。</p>
<p>此外，算法中的OpenList和CloseList其实指的就是已探索区域的边缘和已经探索区域的内部，因此每次进行下一次探索的时候从OpenList里面找出来点作为下一个探索的点即可。而一旦这个点被探索完毕，将其加入到CloseList中即可，即表示当前点已经被考虑过。</p>
<p>最后算法的结束条件就是当终点已经在CloseList中了，表示已经找到了一条路径，此时对CloseList中的点进行回溯即可找到路径，因为CloseList中的探索区域已经蕴含了路径的信息；此外还要注意找不到路径时候的结束条件，避免找不到路径而陷入死循环。</p>
<p>上面是我对于A*算法的理解，如果需要学习A*算法的话，其实B站上、知乎上有很多不错的讲解。这里就贴出来百度百科和维基百科的介绍</p>
<blockquote>
<p><strong>From Wikipedia</strong>：</p>
<p>A<em> (pronounced “A-star”) is a graph traversal and path search algorithm, which is often used in many fields of computer science due to its completeness, optimality, and optimal efficiency. One major practical drawback is its  $O(b^{d}$) space complexity, as it stores all generated nodes in memory. Thus, in practical travel-routing systems, it is generally outperformed by algorithms which can pre-process the graph to attain better performance, as well as memory-bounded approaches; however, A</em> is still the best solution in many cases.</p>
<p><img src="https://jack-1307599355.cos.ap-shanghai.myqcloud.com/img/image-20211222143802336.png" alt="维基百科上对A*算法的介绍"></p>
<p><strong>From BaiduBaike</strong>：</p>
<p>A*算法，A*（A-Star)算法是一种静态路网中求解最短路径最有效的直接搜索方法，也是解决许多搜索问题的有效算法。算法中的距离估算值与实际值越接近，最终搜索速度越快。</p>
<p><img src="https://jack-1307599355.cos.ap-shanghai.myqcloud.com/img/image-20211222143914743.png" alt="百度百科上对A*算法的介绍"></p>
</blockquote>
<h2 id="2-实现思路"><a href="#2-实现思路" class="headerlink" title="2. 实现思路"></a>2. 实现思路</h2><p>针对不同的功能，整个程序的实现，主要分为三个层次（软件分层的思想）：</p>
<ol>
<li><strong>核心层</strong>：负责GUI的显示（地图的绘制与更新）、地图的加载与保存、键盘鼠标等事件对应的回调函数（信号处理函数）的绑定</li>
<li><strong>算法实现层</strong>：负责A*算法的实现</li>
<li><strong>用户界面层</strong>：负责提供命令行用户界面，从而实现<del>高级感</del>（逼格）</li>
</ol>
<h3 id="1-核心层"><a href="#1-核心层" class="headerlink" title="1. 核心层"></a>1. 核心层</h3><p>核心层的具体任务为维护全局地图以及进行地图的保存，因此代码也是围绕这两大内容进行编写的。</p>
<h4 id="1-地图的维护"><a href="#1-地图的维护" class="headerlink" title="1. 地图的维护"></a>1. 地图的维护</h4><p>对于路径规划问题，其核心维护对象就是全局地图地图，因为地图的保存、与加载；GUI的显示以及路径规划的实现都需要地图上区域的状态，因此在核心层首先需要实现的的就是地图。</p>
<ul>
<li>首先是关于地图的表示。对于地图本身而言，由于目前进行的是二维的路径规划，因此可以利用一个二维数组来表示。</li>
<li>其次是地图在磁盘上的表示。为了方便保存之后方便读取、加载以及人类的理解，可以将二维数组保存为csv文件从而序列化到磁盘上，而在加载地图的时候再从磁盘上反序列化csv文件到内存，从而读取出来地图。</li>
<li>最后是地图中障碍物的表示。由于地图中的区域会有多种状态，例如是否为障碍物（是否可行），其次在进行A*路径规划的时候也会为地图中的区域标记其状态（是否已经考虑过）。因此针对地图中不同的状态的区域，使用不同的数值表示当前区域的状态，例如inf表示障碍物，3表示最终规划得到的路径。</li>
</ul>
<h4 id="2-地图的显示"><a href="#2-地图的显示" class="headerlink" title="2. 地图的显示"></a>2. 地图的显示</h4><p>由于地图的显示涉及到图形的显示，因此需要了解一下图形在计算机中的显示。</p>
<blockquote>
<p>图形的显示有两种方式，分别是矢量图以及光栅图。</p>
<ul>
<li>对于矢量图，其内部的图形是由基本的几何图形构成的，因此在矢量图文件（例如.dot）文件中，只需要按照指定的格式描述图形的属性即可。例如Windows的.dot文件，我们按照其要求的语法对图形进行描述，然后对应的解析该语法，利用图形学的算法即可渲染出来图形，我们常见的PDF、SVG等等文件都是矢量图。例如下面的例子</li>
</ul>
<p><img src="https://jack-1307599355.cos.ap-shanghai.myqcloud.com/img/image-20211224005217273.png" alt="矢量图的一种：dot文件"></p>
<ul>
<li>而对于光栅图，其基本构成单位是像素，每个像素大小只有零点几个毫米，而每平方厘米都会有几百几千个像素。而每个像素都会有自己的数值，表现出来自己的颜色。因此我们通过几万个极小的、在人眼看来是点的像素组合起来就成了我们所看到的图像。因此这种图像又称为位图、点阵图、像素图。我们常见的JPG、PNG、BMP等等都是光栅图，例如下面的例子</li>
</ul>
<p><img src="https://bkimg.cdn.bcebos.com/pic/54fbb2fb43166d22356091ba4b2309f79052d28d?x-bce-process=image/watermark,image_d2F0ZXIvYmFpa2U4MA==,g_7,xp_5,yp_5/format,f_auto" alt="经典的光栅图"></p>
<p>矢量图最大的好处就在于由于其图形是完全利用数学公式描述的（例如圆相对于屏幕左上角的相对距离、圆相对于屏幕宽度的半径等等），因此针对不同的屏幕、不同的放大背书，矢量图片完全可以通过运算进行放大、适配。因此在我们用户看来就是矢量图是无论怎样放大边缘都不会模糊。例如下面的pdf</p>
<p><img src="https://jack-1307599355.cos.ap-shanghai.myqcloud.com/img/image-20211224010247748.png" alt="放大2.5倍的PDF文件"></p>
<p>aas</p>
<p>而光栅图的基本单位是像素，因此再怎么放大，像素都是不会变的，因此在放大一定的倍数就会模糊，这个时候即便有一些算法会做自适应，例如双线性插值、三线性插值等等增加像素的数量，但是他们会造成边缘的模糊</p>
<p><img src="https://jack-1307599355.cos.ap-shanghai.myqcloud.com/img/image-20211224010524045.png" alt="光栅图放大后可见的像素"></p>
<p><img src="https://jack-1307599355.cos.ap-shanghai.myqcloud.com/img/image-20211224010559551.png" alt="经过插值处理之后的图片会变的模糊"></p>
<p>因此在不同场景下有不同的取舍。一般而言，当图形比较好描述（都是规则的几何图形）的时候，就会选择用矢量图，而当图形不好描述的时候（例如自然景观），这个时候就会选择光栅图</p>
</blockquote>
<p>尽管地图都是规整的矩形和色块，使用矢量图非常容易描述，但是考虑到如果需要使用矢量图像的话还需要不少的学习成本来学习矢量图的描述语言，花费的时间比较多。而有考虑到Python中其实已经想Matplotlib、Seaborn、Plotly这类非常好的光栅图绘图库（当然他们可以绘制矢量图），因此最终决定使用光栅图来显示、绘制地图。</p>
<p>当然，其实Matplotlib、Plotly这些库最终调用的都是类似于cairo、gtk这些由C/C++开发出来的图形库</p>
<h4 id="3-地图动态显示"><a href="#3-地图动态显示" class="headerlink" title="3. 地图动态显示"></a>3. 地图动态显示</h4><p>地图的绘制与显示实际上是一个非常消耗资源的操作。上面的GIF和后面放出来的B站的演示视频里A*算法花了不少的时间最后才找到最终的路径，但是真正的纯A<em>算法的规划路径的速度才只有0.2秒左右，这还是我在100\</em>100的地图上测试的。然而为了显示出A*的动态效果图，因此算法的每次试探都会进行地图的绘制。而每次绘图就需要占去0.2秒左右的时间（我读取系统时间做了benchmark）。因此只敢显示30*30的地图。</p>
<p>因此为了尽可能的的加快绘图的速度，在图形中对所有的Patch（即一个小方格）进行记录，每次只会重新绘制发生了变化的Patch而不会重新绘制整张地图，因此极大地加快了显示的速度。至少在我测试的50*50的场景下效果还是非常不错的。</p>
<h3 id="2-算法实现层"><a href="#2-算法实现层" class="headerlink" title="2. 算法实现层"></a>2. 算法实现层</h3><p>算法实现层负责实现A*算法。A*算法中使用使用OpenList以及CloseList维护已探索区域和边缘区域。此外为实现算法实现层与核心层解耦合，而二维地图的状 态的维护由核心层提供，因此在算法实现层只需要调用核心层提供的接口进行地图状态修改即可 </p>
<h3 id="3-用户界面层"><a href="#3-用户界面层" class="headerlink" title="3. 用户界面层"></a>3. 用户界面层</h3><p>用户界面层负责GUI的显示以及命令行用户界面。GUI部分通过Matplotlib内嵌的信号与槽机制实现用户鼠标、键盘事件的监听以及回调函数的绑定，进而响应用户事件，完成功能，例如：保存地图 。命令行用户界面负责根绝接收到不同的用户参数，运行不同的功能，例如绘制地图、开始路径规划……</p>
<h2 id="3-具体代码"><a href="#3-具体代码" class="headerlink" title="3. 具体代码"></a>3. 具体代码</h2><h3 id="1-导入库"><a href="#1-导入库" class="headerlink" title="1. 导入库"></a>1. 导入库</h3><p>导入Python中队列维护的库queue、路径处理库pathlib、二维数组维护库Numpy、csv序列化与反序列化Pandas库、绘图库Matplotlib以及命令行彩色字体库colorama</p>
<pre class="line-numbers language-python"><code class="language-python"><span class="token keyword">import</span> time
<span class="token keyword">import</span> queue
<span class="token keyword">import</span> pprint
<span class="token keyword">import</span> argparse
<span class="token keyword">from</span> typing <span class="token keyword">import</span> <span class="token operator">*</span>
<span class="token keyword">from</span> pathlib <span class="token keyword">import</span> Path
<span class="token keyword">from</span> collections <span class="token keyword">import</span> namedtuple

<span class="token keyword">import</span> numpy <span class="token keyword">as</span> np
<span class="token keyword">import</span> pandas <span class="token keyword">as</span> pd
<span class="token keyword">import</span> matplotlib<span class="token punctuation">.</span>pyplot <span class="token keyword">as</span> plt
<span class="token keyword">import</span> matplotlib<span class="token punctuation">.</span>backend_bases <span class="token keyword">as</span> bbase

<span class="token keyword">from</span> colorama <span class="token keyword">import</span> Fore<span class="token punctuation">,</span> Style
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h3 id="2-核心对象"><a href="#2-核心对象" class="headerlink" title="2. 核心对象"></a>2. 核心对象</h3><p>_MapBase中维护的核心对象为map，程序所处的状态由一个有限状态机维护，不同的事件由不同的回调函数负责处理。</p>
<p>首先，__del__、new、update、add_patch实现了GUI图形的绘制以及更新</p>
<p>pandasfy与depandasfy负责将二维地图以csv文件格式保存至磁盘上</p>
<p>_btn_press_cb、_btn_release_cb、_move_cb、_keyboard_cb分别响应鼠标按下、松开、移动以及键盘按下事件</p>
<pre class="line-numbers language-python"><code class="language-python"><span class="token keyword">class</span> <span class="token class-name">_MapBase</span><span class="token punctuation">(</span>object<span class="token punctuation">)</span><span class="token punctuation">:</span>
    <span class="token triple-quoted-string string">"""
    Notes:
        MapBase 用于可视化的地图创建
    Args:
        mapsize (tuple[int, int]): size of map
        figsize (tuple[int, int]): size of figure
    """</span>

    <span class="token keyword">def</span> <span class="token function">__init__</span><span class="token punctuation">(</span>self<span class="token punctuation">,</span> mapsize<span class="token punctuation">:</span> Tuple<span class="token punctuation">[</span>int<span class="token punctuation">,</span> int<span class="token punctuation">]</span><span class="token punctuation">,</span> figsize<span class="token punctuation">:</span> Tuple<span class="token punctuation">[</span>int<span class="token punctuation">,</span> int<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token punctuation">(</span><span class="token number">12</span><span class="token punctuation">,</span> <span class="token number">12</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">:</span>
        super<span class="token punctuation">(</span>_MapBase<span class="token punctuation">,</span> self<span class="token punctuation">)</span><span class="token punctuation">.</span>__init__<span class="token punctuation">(</span><span class="token punctuation">)</span>
        <span class="token comment" spellcheck="true"># meta information</span>
        self<span class="token punctuation">.</span>_mapsize<span class="token punctuation">:</span> Tuple<span class="token punctuation">[</span>int<span class="token punctuation">,</span> int<span class="token punctuation">]</span> <span class="token operator">=</span> mapsize
        self<span class="token punctuation">.</span>_figsize<span class="token punctuation">:</span> Tuple<span class="token punctuation">[</span>int<span class="token punctuation">,</span> int<span class="token punctuation">]</span> <span class="token operator">=</span> figsize

        <span class="token comment" spellcheck="true"># map, inf obstacle, 0 accessible, 1 in path</span>
        self<span class="token punctuation">.</span>map<span class="token punctuation">:</span> np<span class="token punctuation">.</span>ndarray <span class="token operator">=</span> np<span class="token punctuation">.</span>zeros<span class="token punctuation">(</span>shape<span class="token operator">=</span>mapsize<span class="token punctuation">)</span>
        self<span class="token punctuation">.</span>map_temp<span class="token punctuation">:</span> np<span class="token punctuation">.</span>ndarray <span class="token operator">=</span> None

        <span class="token comment" spellcheck="true"># visualize core object</span>
        self<span class="token punctuation">.</span>_figure<span class="token punctuation">,</span> self<span class="token punctuation">.</span>_axes <span class="token operator">=</span> plt<span class="token punctuation">.</span>subplots<span class="token punctuation">(</span>figsize<span class="token operator">=</span>figsize<span class="token punctuation">)</span>
        self<span class="token punctuation">.</span>_canvas <span class="token operator">=</span> self<span class="token punctuation">.</span>_figure<span class="token punctuation">.</span>canvas
        self<span class="token punctuation">.</span>_title<span class="token punctuation">:</span> plt<span class="token punctuation">.</span>Text <span class="token operator">=</span> None
        self<span class="token punctuation">.</span>_go_on<span class="token punctuation">:</span> bool <span class="token operator">=</span> <span class="token boolean">False</span>

        <span class="token comment" spellcheck="true"># gui interaction, finite state machine to control plot</span>
        self<span class="token punctuation">.</span>_on_press<span class="token punctuation">:</span> bool <span class="token operator">=</span> <span class="token boolean">False</span>
        self<span class="token punctuation">.</span>_current_state <span class="token operator">=</span> <span class="token string">"add_obstacle"</span>
        self<span class="token punctuation">.</span>btn_pressed_cid <span class="token operator">=</span> self<span class="token punctuation">.</span>_canvas<span class="token punctuation">.</span>mpl_connect<span class="token punctuation">(</span><span class="token string">"button_press_event"</span><span class="token punctuation">,</span> self<span class="token punctuation">.</span>_btn_press_cb<span class="token punctuation">)</span>
        self<span class="token punctuation">.</span>btn_released_cid <span class="token operator">=</span> self<span class="token punctuation">.</span>_canvas<span class="token punctuation">.</span>mpl_connect<span class="token punctuation">(</span><span class="token string">"button_release_event"</span><span class="token punctuation">,</span> self<span class="token punctuation">.</span>_btn_release_cb<span class="token punctuation">)</span>
        self<span class="token punctuation">.</span>mouse_move_cid <span class="token operator">=</span> self<span class="token punctuation">.</span>_canvas<span class="token punctuation">.</span>mpl_connect<span class="token punctuation">(</span><span class="token string">"motion_notify_event"</span><span class="token punctuation">,</span> self<span class="token punctuation">.</span>_move_cb<span class="token punctuation">)</span>
        self<span class="token punctuation">.</span>keyboard_cid <span class="token operator">=</span> self<span class="token punctuation">.</span>_canvas<span class="token punctuation">.</span>mpl_connect<span class="token punctuation">(</span><span class="token string">"key_press_event"</span><span class="token punctuation">,</span> self<span class="token punctuation">.</span>_keyboard_cb<span class="token punctuation">)</span>

        self<span class="token punctuation">.</span>new<span class="token punctuation">(</span><span class="token punctuation">)</span>

    <span class="token keyword">def</span> <span class="token function">__del__</span><span class="token punctuation">(</span>self<span class="token punctuation">)</span><span class="token punctuation">:</span>
        plt<span class="token punctuation">.</span>close<span class="token punctuation">(</span>self<span class="token punctuation">.</span>_figure<span class="token punctuation">)</span>

    <span class="token keyword">def</span> <span class="token function">start</span><span class="token punctuation">(</span>self<span class="token punctuation">)</span><span class="token punctuation">:</span>
        <span class="token keyword">assert</span> <span class="token boolean">False</span><span class="token punctuation">,</span> f<span class="token string">"This method should be overwritten by subclass"</span>

    <span class="token keyword">def</span> <span class="token function">update</span><span class="token punctuation">(</span>self<span class="token punctuation">)</span><span class="token punctuation">:</span>
        self<span class="token punctuation">.</span>_canvas<span class="token punctuation">.</span>draw_idle<span class="token punctuation">(</span><span class="token punctuation">)</span>

    <span class="token keyword">def</span> <span class="token function">new</span><span class="token punctuation">(</span>self<span class="token punctuation">)</span> <span class="token operator">-</span><span class="token operator">></span> bool<span class="token punctuation">:</span>
        <span class="token triple-quoted-string string">"""
        Notes:
            new is used to clear the map. In practice, generate a new axes
        Returns:
            if_clear (bool): true if successfully clear the map
        """</span>
        <span class="token keyword">try</span><span class="token punctuation">:</span>
            self<span class="token punctuation">.</span>map <span class="token operator">=</span> np<span class="token punctuation">.</span>zeros<span class="token punctuation">(</span>shape<span class="token operator">=</span>self<span class="token punctuation">.</span>_mapsize<span class="token punctuation">)</span>
            self<span class="token punctuation">.</span>_axes<span class="token punctuation">.</span>cla<span class="token punctuation">(</span><span class="token punctuation">)</span>
            self<span class="token punctuation">.</span>_axes<span class="token punctuation">.</span>grid<span class="token punctuation">(</span><span class="token boolean">True</span><span class="token punctuation">)</span>
            self<span class="token punctuation">.</span>_axes<span class="token punctuation">.</span>set_xticks<span class="token punctuation">(</span>range<span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">,</span> self<span class="token punctuation">.</span>_mapsize<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span> <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">)</span>
            self<span class="token punctuation">.</span>_axes<span class="token punctuation">.</span>set_yticks<span class="token punctuation">(</span>range<span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">,</span> self<span class="token punctuation">.</span>_mapsize<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">)</span>
            self<span class="token punctuation">.</span>_axes<span class="token punctuation">.</span>set_xlim<span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">,</span> self<span class="token punctuation">.</span>_mapsize<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">)</span>
            self<span class="token punctuation">.</span>_axes<span class="token punctuation">.</span>set_ylim<span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">,</span> self<span class="token punctuation">.</span>_mapsize<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">)</span>
            self<span class="token punctuation">.</span>_title <span class="token operator">=</span> self<span class="token punctuation">.</span>_axes<span class="token punctuation">.</span>set_title<span class="token punctuation">(</span>f<span class="token string">"Current State: {self._current_state}"</span><span class="token punctuation">)</span>
            self<span class="token punctuation">.</span>_axes<span class="token punctuation">.</span>scatter<span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">,</span> marker<span class="token operator">=</span><span class="token string">"s"</span><span class="token punctuation">,</span> c<span class="token operator">=</span><span class="token string">"red"</span><span class="token punctuation">,</span> label<span class="token operator">=</span><span class="token string">"goal"</span><span class="token punctuation">)</span>
            self<span class="token punctuation">.</span>_axes<span class="token punctuation">.</span>scatter<span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">,</span> marker<span class="token operator">=</span><span class="token string">"s"</span><span class="token punctuation">,</span> c<span class="token operator">=</span><span class="token string">"black"</span><span class="token punctuation">,</span> label<span class="token operator">=</span><span class="token string">"obstacle"</span><span class="token punctuation">)</span>
            self<span class="token punctuation">.</span>_axes<span class="token punctuation">.</span>scatter<span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">,</span> marker<span class="token operator">=</span><span class="token string">"s"</span><span class="token punctuation">,</span> c<span class="token operator">=</span><span class="token string">"green"</span><span class="token punctuation">,</span> label<span class="token operator">=</span><span class="token string">"start"</span><span class="token punctuation">)</span>
            self<span class="token punctuation">.</span>_axes<span class="token punctuation">.</span>scatter<span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">,</span> marker<span class="token operator">=</span><span class="token string">"s"</span><span class="token punctuation">,</span> c<span class="token operator">=</span><span class="token string">"blue"</span><span class="token punctuation">,</span> label<span class="token operator">=</span><span class="token string">"final path"</span><span class="token punctuation">)</span>
            self<span class="token punctuation">.</span>_axes<span class="token punctuation">.</span>scatter<span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">,</span> marker<span class="token operator">=</span><span class="token string">"s"</span><span class="token punctuation">,</span> c<span class="token operator">=</span><span class="token string">"gray"</span><span class="token punctuation">,</span> label<span class="token operator">=</span><span class="token string">"explored"</span><span class="token punctuation">)</span>
            self<span class="token punctuation">.</span>_axes<span class="token punctuation">.</span>scatter<span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">,</span> marker<span class="token operator">=</span><span class="token string">"s"</span><span class="token punctuation">,</span> c<span class="token operator">=</span><span class="token string">"cyan"</span><span class="token punctuation">,</span> label<span class="token operator">=</span><span class="token string">"frontier"</span><span class="token punctuation">)</span>
            self<span class="token punctuation">.</span>_axes<span class="token punctuation">.</span>legend<span class="token punctuation">(</span>loc<span class="token operator">=</span><span class="token punctuation">(</span><span class="token number">1.01</span><span class="token punctuation">,</span> <span class="token number">0.85</span><span class="token punctuation">)</span><span class="token punctuation">)</span>
            self<span class="token punctuation">.</span>update<span class="token punctuation">(</span><span class="token punctuation">)</span>
            <span class="token keyword">return</span> <span class="token boolean">True</span>
        <span class="token keyword">except</span> KeyboardInterrupt <span class="token keyword">as</span> e<span class="token punctuation">:</span>
            <span class="token keyword">print</span><span class="token punctuation">(</span><span class="token string">"Keyboard interrupted"</span><span class="token punctuation">)</span>
            <span class="token keyword">return</span> <span class="token boolean">False</span>

    <span class="token keyword">def</span> <span class="token function">add_patch</span><span class="token punctuation">(</span>self<span class="token punctuation">,</span> x<span class="token punctuation">:</span> Union<span class="token punctuation">[</span>int<span class="token punctuation">,</span> np<span class="token punctuation">.</span>ndarray<span class="token punctuation">,</span> list<span class="token punctuation">]</span><span class="token punctuation">,</span> y<span class="token punctuation">:</span> Union<span class="token punctuation">[</span>int<span class="token punctuation">,</span> np<span class="token punctuation">.</span>ndarray<span class="token punctuation">,</span> list<span class="token punctuation">]</span><span class="token punctuation">,</span>
                  patches<span class="token punctuation">:</span> Union<span class="token punctuation">[</span>str<span class="token punctuation">,</span> None<span class="token punctuation">]</span> <span class="token operator">=</span> None<span class="token punctuation">)</span> <span class="token operator">-</span><span class="token operator">></span> bool<span class="token punctuation">:</span>
        prompt <span class="token operator">=</span> <span class="token punctuation">(</span>x<span class="token punctuation">,</span> y<span class="token punctuation">)</span> <span class="token keyword">if</span> isinstance<span class="token punctuation">(</span>x<span class="token punctuation">,</span> int<span class="token punctuation">)</span> <span class="token keyword">else</span> list<span class="token punctuation">(</span>zip<span class="token punctuation">(</span>x<span class="token punctuation">,</span> y<span class="token punctuation">)</span><span class="token punctuation">)</span>
        <span class="token keyword">if</span> self<span class="token punctuation">.</span>_current_state <span class="token operator">==</span> <span class="token string">"add_obstacle"</span><span class="token punctuation">:</span>
            <span class="token keyword">try</span><span class="token punctuation">:</span>
                self<span class="token punctuation">.</span>map<span class="token punctuation">[</span>x<span class="token punctuation">,</span> y<span class="token punctuation">]</span> <span class="token operator">=</span> np<span class="token punctuation">.</span>inf
            <span class="token keyword">except</span> IndexError<span class="token punctuation">:</span>
                <span class="token keyword">pass</span>
            self<span class="token punctuation">.</span>_axes<span class="token punctuation">.</span>scatter<span class="token punctuation">(</span>x <span class="token operator">+</span> <span class="token number">0.5</span><span class="token punctuation">,</span> y <span class="token operator">+</span> <span class="token number">0.5</span><span class="token punctuation">,</span> s<span class="token operator">=</span><span class="token number">200</span><span class="token punctuation">,</span> marker<span class="token operator">=</span><span class="token string">"s"</span><span class="token punctuation">,</span> c<span class="token operator">=</span><span class="token string">"black"</span><span class="token punctuation">)</span>
            <span class="token keyword">print</span><span class="token punctuation">(</span>f<span class="token string">"Add obstacle: {prompt}"</span><span class="token punctuation">)</span>
        <span class="token keyword">elif</span> self<span class="token punctuation">.</span>_current_state <span class="token operator">==</span> <span class="token string">"add_goal"</span><span class="token punctuation">:</span>
            <span class="token keyword">if</span> <span class="token punctuation">(</span>self<span class="token punctuation">.</span>map <span class="token operator">==</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">.</span>any<span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">:</span>
                <span class="token keyword">print</span><span class="token punctuation">(</span>f<span class="token string">"{Fore.YELLOW}Already have one goal!{Style.RESET_ALL}"</span><span class="token punctuation">)</span>
                <span class="token keyword">return</span> <span class="token boolean">False</span>
            self<span class="token punctuation">.</span>map<span class="token punctuation">[</span>x<span class="token punctuation">,</span> y<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token operator">-</span><span class="token number">1</span>
            self<span class="token punctuation">.</span>_axes<span class="token punctuation">.</span>scatter<span class="token punctuation">(</span>x <span class="token operator">+</span> <span class="token number">0.5</span><span class="token punctuation">,</span> y <span class="token operator">+</span> <span class="token number">0.5</span><span class="token punctuation">,</span> s<span class="token operator">=</span><span class="token number">200</span><span class="token punctuation">,</span> marker<span class="token operator">=</span><span class="token string">"s"</span><span class="token punctuation">,</span> c<span class="token operator">=</span><span class="token string">"red"</span><span class="token punctuation">)</span>
            <span class="token keyword">print</span><span class="token punctuation">(</span>f<span class="token string">"Add goal: {prompt}"</span><span class="token punctuation">)</span>
        <span class="token keyword">elif</span> self<span class="token punctuation">.</span>_current_state <span class="token operator">==</span> <span class="token string">"add_start"</span><span class="token punctuation">:</span>
            <span class="token keyword">if</span> <span class="token punctuation">(</span>self<span class="token punctuation">.</span>map <span class="token operator">==</span> <span class="token operator">-</span><span class="token number">2</span><span class="token punctuation">)</span><span class="token punctuation">.</span>any<span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">:</span>
                <span class="token keyword">print</span><span class="token punctuation">(</span>f<span class="token string">"{Fore.YELLOW}Already have one start!{Style.RESET_ALL}"</span><span class="token punctuation">)</span>
                <span class="token keyword">return</span> <span class="token boolean">False</span>
            self<span class="token punctuation">.</span>map<span class="token punctuation">[</span>x<span class="token punctuation">,</span> y<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token operator">-</span><span class="token number">2</span>
            self<span class="token punctuation">.</span>_axes<span class="token punctuation">.</span>scatter<span class="token punctuation">(</span>x <span class="token operator">+</span> <span class="token number">0.5</span><span class="token punctuation">,</span> y <span class="token operator">+</span> <span class="token number">0.5</span><span class="token punctuation">,</span> s<span class="token operator">=</span><span class="token number">200</span><span class="token punctuation">,</span> marker<span class="token operator">=</span><span class="token string">"s"</span><span class="token punctuation">,</span> c<span class="token operator">=</span><span class="token string">"green"</span><span class="token punctuation">)</span>
            <span class="token keyword">print</span><span class="token punctuation">(</span>f<span class="token string">"Add start: {prompt}"</span><span class="token punctuation">)</span>
        <span class="token keyword">elif</span> self<span class="token punctuation">.</span>_current_state <span class="token operator">==</span> <span class="token string">"going_back"</span><span class="token punctuation">:</span>
            self<span class="token punctuation">.</span>map<span class="token punctuation">[</span>x<span class="token punctuation">,</span> y<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token operator">-</span><span class="token number">3</span>
            self<span class="token punctuation">.</span>_axes<span class="token punctuation">.</span>scatter<span class="token punctuation">(</span>x <span class="token operator">+</span> <span class="token number">0.5</span><span class="token punctuation">,</span> y <span class="token operator">+</span> <span class="token number">0.5</span><span class="token punctuation">,</span> s<span class="token operator">=</span><span class="token number">200</span><span class="token punctuation">,</span> marker<span class="token operator">=</span><span class="token string">"s"</span><span class="token punctuation">,</span> c<span class="token operator">=</span><span class="token string">"blue"</span><span class="token punctuation">)</span>
        <span class="token keyword">elif</span> self<span class="token punctuation">.</span>_current_state <span class="token operator">==</span> <span class="token string">"clear_patch"</span><span class="token punctuation">:</span>
            <span class="token keyword">if</span> self<span class="token punctuation">.</span>map<span class="token punctuation">[</span>x<span class="token punctuation">,</span> y<span class="token punctuation">]</span> <span class="token operator">==</span> <span class="token number">0</span><span class="token punctuation">:</span>
                <span class="token keyword">print</span><span class="token punctuation">(</span>f<span class="token string">"{Fore.YELLOW}Not in use!{Style.RESET_ALL}"</span><span class="token punctuation">)</span>
                <span class="token keyword">return</span> <span class="token boolean">False</span>
            self<span class="token punctuation">.</span>map<span class="token punctuation">[</span>x<span class="token punctuation">,</span> y<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">0</span>
            self<span class="token punctuation">.</span>_axes<span class="token punctuation">.</span>scatter<span class="token punctuation">(</span>x <span class="token operator">+</span> <span class="token number">0.5</span><span class="token punctuation">,</span> y <span class="token operator">+</span> <span class="token number">0.5</span><span class="token punctuation">,</span> s<span class="token operator">=</span><span class="token number">250</span><span class="token punctuation">,</span> marker<span class="token operator">=</span><span class="token string">"s"</span><span class="token punctuation">,</span> c<span class="token operator">=</span><span class="token string">"white"</span><span class="token punctuation">)</span>
            <span class="token keyword">print</span><span class="token punctuation">(</span>f<span class="token string">"Cleared: {prompt}"</span><span class="token punctuation">)</span>
        <span class="token keyword">elif</span> self<span class="token punctuation">.</span>_current_state <span class="token operator">==</span> <span class="token string">"searching"</span><span class="token punctuation">:</span>
            <span class="token keyword">if</span> patches <span class="token operator">==</span> <span class="token string">"explored"</span><span class="token punctuation">:</span>
                <span class="token comment" spellcheck="true"># assert (0 &lt;= self.map[x, y] &lt;= 2).all(), f"{Fore.RED}Illegal Operation on map{Fore.RESET}"</span>
                <span class="token comment" spellcheck="true"># self.map[x, y] = 1</span>
                self<span class="token punctuation">.</span>_axes<span class="token punctuation">.</span>scatter<span class="token punctuation">(</span>x <span class="token operator">+</span> <span class="token number">0.5</span><span class="token punctuation">,</span> y <span class="token operator">+</span> <span class="token number">0.5</span><span class="token punctuation">,</span> s<span class="token operator">=</span><span class="token number">200</span><span class="token punctuation">,</span> marker<span class="token operator">=</span><span class="token string">"s"</span><span class="token punctuation">,</span> c<span class="token operator">=</span><span class="token string">"gray"</span><span class="token punctuation">,</span> alpha<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">)</span>
            <span class="token keyword">elif</span> patches <span class="token operator">==</span> <span class="token string">"frontier"</span><span class="token punctuation">:</span>
                <span class="token comment" spellcheck="true"># assert (0 &lt;= self.map[x, y] &lt;= 2).all(), f"{Fore.RED}Illegal Operation on map{Fore.RESET}"</span>
                <span class="token comment" spellcheck="true"># self.map[x, y] = 2</span>
                self<span class="token punctuation">.</span>_axes<span class="token punctuation">.</span>scatter<span class="token punctuation">(</span>x <span class="token operator">+</span> <span class="token number">0.5</span><span class="token punctuation">,</span> y <span class="token operator">+</span> <span class="token number">0.5</span><span class="token punctuation">,</span> s<span class="token operator">=</span><span class="token number">200</span><span class="token punctuation">,</span> marker<span class="token operator">=</span><span class="token string">"s"</span><span class="token punctuation">,</span> c<span class="token operator">=</span><span class="token string">"cyan"</span><span class="token punctuation">,</span> alpha<span class="token operator">=</span><span class="token number">1</span><span class="token punctuation">)</span>
        <span class="token keyword">else</span><span class="token punctuation">:</span>
            <span class="token keyword">assert</span> <span class="token boolean">False</span><span class="token punctuation">,</span> F<span class="token string">"{Fore.RED}Invalid State: {self._current_state}"</span>
        self<span class="token punctuation">.</span>update<span class="token punctuation">(</span><span class="token punctuation">)</span>
        <span class="token keyword">return</span> <span class="token boolean">True</span>

    <span class="token keyword">def</span> <span class="token function">pandasfy</span><span class="token punctuation">(</span>self<span class="token punctuation">)</span> <span class="token operator">-</span><span class="token operator">></span> pd<span class="token punctuation">.</span>DataFrame<span class="token punctuation">:</span>
        <span class="token triple-quoted-string string">"""
        Notes:
            pandasfy will serialize current map from matplotlib to cvs file
        Returns:
            serialized_map (pd.Dataframe)
        """</span>
        pp<span class="token punctuation">:</span> pd<span class="token punctuation">.</span>DataFrame <span class="token operator">=</span> pd<span class="token punctuation">.</span>DataFrame<span class="token punctuation">(</span>self<span class="token punctuation">.</span>map<span class="token punctuation">.</span>copy<span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">.</span>T<span class="token punctuation">[</span><span class="token punctuation">:</span><span class="token punctuation">:</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">,</span> <span class="token punctuation">:</span><span class="token punctuation">]</span><span class="token punctuation">,</span> dtype<span class="token operator">=</span>str<span class="token punctuation">)</span>
        pp<span class="token punctuation">.</span>replace<span class="token punctuation">(</span><span class="token string">"-1.0"</span><span class="token punctuation">,</span> <span class="token string">"GOAL"</span><span class="token punctuation">,</span> inplace<span class="token operator">=</span><span class="token boolean">True</span><span class="token punctuation">)</span>
        pp<span class="token punctuation">.</span>replace<span class="token punctuation">(</span><span class="token string">"-2.0"</span><span class="token punctuation">,</span> <span class="token string">"START"</span><span class="token punctuation">,</span> inplace<span class="token operator">=</span><span class="token boolean">True</span><span class="token punctuation">)</span>
        <span class="token keyword">return</span> pp

    <span class="token keyword">def</span> <span class="token function">depandasfy</span><span class="token punctuation">(</span>self<span class="token punctuation">,</span> csv_path<span class="token punctuation">:</span> Path<span class="token punctuation">)</span><span class="token punctuation">:</span>
        <span class="token triple-quoted-string string">"""
        Notes:
            depandasfy will deserialized csv file map to matplotlib
        Args:
            csv_path (Path): path of csv file
        Returns:
            None
        """</span>
        df<span class="token punctuation">:</span> pd<span class="token punctuation">.</span>DataFrame <span class="token operator">=</span> pd<span class="token punctuation">.</span>read_csv<span class="token punctuation">(</span>filepath_or_buffer<span class="token operator">=</span>csv_path<span class="token punctuation">,</span> index_col<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">,</span> header<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">)</span>
        df<span class="token punctuation">.</span>replace<span class="token punctuation">(</span><span class="token string">"START"</span><span class="token punctuation">,</span> <span class="token string">"-2.0"</span><span class="token punctuation">,</span> inplace<span class="token operator">=</span><span class="token boolean">True</span><span class="token punctuation">)</span>
        df<span class="token punctuation">.</span>replace<span class="token punctuation">(</span><span class="token string">"GOAL"</span><span class="token punctuation">,</span> <span class="token string">"-1.0"</span><span class="token punctuation">,</span> inplace<span class="token operator">=</span><span class="token boolean">True</span><span class="token punctuation">)</span>
        self<span class="token punctuation">.</span>new<span class="token punctuation">(</span><span class="token punctuation">)</span>
        t <span class="token operator">=</span> df<span class="token punctuation">.</span>to_numpy<span class="token punctuation">(</span>dtype<span class="token operator">=</span>np<span class="token punctuation">.</span>float64<span class="token punctuation">)</span><span class="token punctuation">[</span><span class="token punctuation">:</span><span class="token punctuation">:</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">,</span> <span class="token punctuation">:</span><span class="token punctuation">]</span><span class="token punctuation">.</span>T
        <span class="token comment" spellcheck="true"># self.map = df.to_numpy()</span>
        xs<span class="token punctuation">,</span> ys <span class="token operator">=</span> np<span class="token punctuation">.</span>where<span class="token punctuation">(</span>t <span class="token operator">==</span> np<span class="token punctuation">.</span>inf<span class="token punctuation">)</span>
        self<span class="token punctuation">.</span>_current_state <span class="token operator">=</span> <span class="token string">"add_obstacle"</span>
        self<span class="token punctuation">.</span>add_patch<span class="token punctuation">(</span>xs<span class="token punctuation">,</span> ys<span class="token punctuation">)</span>
        xs<span class="token punctuation">,</span> ys <span class="token operator">=</span> np<span class="token punctuation">.</span>where<span class="token punctuation">(</span>t <span class="token operator">==</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span>
        self<span class="token punctuation">.</span>_current_state <span class="token operator">=</span> <span class="token string">"add_goal"</span>
        self<span class="token punctuation">.</span>add_patch<span class="token punctuation">(</span>xs<span class="token punctuation">,</span> ys<span class="token punctuation">)</span>
        xs<span class="token punctuation">,</span> ys <span class="token operator">=</span> np<span class="token punctuation">.</span>where<span class="token punctuation">(</span>t <span class="token operator">==</span> <span class="token operator">-</span><span class="token number">2</span><span class="token punctuation">)</span>
        self<span class="token punctuation">.</span>_current_state <span class="token operator">=</span> <span class="token string">"add_start"</span>
        self<span class="token punctuation">.</span>add_patch<span class="token punctuation">(</span>xs<span class="token punctuation">,</span> ys<span class="token punctuation">)</span>

    <span class="token keyword">def</span> <span class="token function">_update_title</span><span class="token punctuation">(</span>self<span class="token punctuation">,</span> s<span class="token punctuation">:</span> str <span class="token operator">=</span> None<span class="token punctuation">)</span><span class="token punctuation">:</span>
        <span class="token keyword">if</span> s <span class="token keyword">is</span> None<span class="token punctuation">:</span>
            self<span class="token punctuation">.</span>_title<span class="token punctuation">.</span>set_text<span class="token punctuation">(</span>f<span class="token string">"Current State: {self._current_state}"</span><span class="token punctuation">)</span>
        <span class="token keyword">else</span><span class="token punctuation">:</span>
            self<span class="token punctuation">.</span>_title<span class="token punctuation">.</span>set_text<span class="token punctuation">(</span>s<span class="token punctuation">)</span>
        self<span class="token punctuation">.</span>update<span class="token punctuation">(</span><span class="token punctuation">)</span>

    <span class="token keyword">def</span> <span class="token function">_btn_press_cb</span><span class="token punctuation">(</span>self<span class="token punctuation">,</span> event<span class="token punctuation">:</span> bbase<span class="token punctuation">.</span>MouseEvent<span class="token punctuation">)</span> <span class="token operator">-</span><span class="token operator">></span> None<span class="token punctuation">:</span>
        self<span class="token punctuation">.</span>_on_press <span class="token operator">=</span> <span class="token boolean">True</span>
        <span class="token keyword">if</span> event<span class="token punctuation">.</span>inaxes<span class="token punctuation">:</span>
            point <span class="token operator">=</span> <span class="token punctuation">(</span>int<span class="token punctuation">(</span>event<span class="token punctuation">.</span>xdata<span class="token punctuation">)</span><span class="token punctuation">,</span> int<span class="token punctuation">(</span>event<span class="token punctuation">.</span>ydata<span class="token punctuation">)</span><span class="token punctuation">)</span>
            self<span class="token punctuation">.</span>add_patch<span class="token punctuation">(</span><span class="token operator">*</span>point<span class="token punctuation">)</span>

    <span class="token keyword">def</span> <span class="token function">_btn_release_cb</span><span class="token punctuation">(</span>self<span class="token punctuation">,</span> event<span class="token punctuation">:</span> bbase<span class="token punctuation">.</span>MouseEvent<span class="token punctuation">)</span> <span class="token operator">-</span><span class="token operator">></span> None<span class="token punctuation">:</span>
        self<span class="token punctuation">.</span>_on_press <span class="token operator">=</span> <span class="token boolean">False</span>

    <span class="token keyword">def</span> <span class="token function">_move_cb</span><span class="token punctuation">(</span>self<span class="token punctuation">,</span> event<span class="token punctuation">:</span> bbase<span class="token punctuation">.</span>MouseEvent<span class="token punctuation">)</span> <span class="token operator">-</span><span class="token operator">></span> None<span class="token punctuation">:</span>
        <span class="token keyword">if</span> self<span class="token punctuation">.</span>_on_press<span class="token punctuation">:</span>
            <span class="token keyword">if</span> event<span class="token punctuation">.</span>inaxes<span class="token punctuation">:</span>
                point <span class="token operator">=</span> <span class="token punctuation">(</span>int<span class="token punctuation">(</span>event<span class="token punctuation">.</span>xdata<span class="token punctuation">)</span><span class="token punctuation">,</span> int<span class="token punctuation">(</span>event<span class="token punctuation">.</span>ydata<span class="token punctuation">)</span><span class="token punctuation">)</span>
                self<span class="token punctuation">.</span>add_patch<span class="token punctuation">(</span><span class="token operator">*</span>point<span class="token punctuation">)</span>

    <span class="token keyword">def</span> <span class="token function">_keyboard_cb</span><span class="token punctuation">(</span>self<span class="token punctuation">,</span> event<span class="token punctuation">:</span> bbase<span class="token punctuation">.</span>KeyEvent<span class="token punctuation">)</span><span class="token punctuation">:</span>
        <span class="token keyword">if</span> event<span class="token punctuation">.</span>key <span class="token operator">==</span> <span class="token string">"c"</span><span class="token punctuation">:</span>
            self<span class="token punctuation">.</span>_current_state <span class="token operator">=</span> <span class="token string">"add_obstacle"</span>
            <span class="token keyword">print</span><span class="token punctuation">(</span>f<span class="token string">"{Fore.YELLOW}Clear all!{Style.RESET_ALL}"</span><span class="token punctuation">)</span>
            self<span class="token punctuation">.</span>new<span class="token punctuation">(</span><span class="token punctuation">)</span>
        <span class="token keyword">elif</span> event<span class="token punctuation">.</span>key <span class="token operator">==</span> <span class="token string">"1"</span><span class="token punctuation">:</span>
            self<span class="token punctuation">.</span>_current_state <span class="token operator">=</span> <span class="token string">"add_obstacle"</span>
            <span class="token keyword">print</span><span class="token punctuation">(</span>f<span class="token string">"{Fore.GREEN}Switch to {self._current_state}{Style.RESET_ALL}"</span><span class="token punctuation">)</span>
        <span class="token keyword">elif</span> event<span class="token punctuation">.</span>key <span class="token operator">==</span> <span class="token string">"2"</span><span class="token punctuation">:</span>
            self<span class="token punctuation">.</span>_current_state <span class="token operator">=</span> <span class="token string">"add_goal"</span>
            <span class="token keyword">print</span><span class="token punctuation">(</span>f<span class="token string">"{Fore.GREEN}Switch to {self._current_state}{Style.RESET_ALL}"</span><span class="token punctuation">)</span>
        <span class="token keyword">elif</span> event<span class="token punctuation">.</span>key <span class="token operator">==</span> <span class="token string">"3"</span><span class="token punctuation">:</span>
            self<span class="token punctuation">.</span>_current_state <span class="token operator">=</span> <span class="token string">"add_start"</span>
            <span class="token keyword">print</span><span class="token punctuation">(</span>f<span class="token string">"{Fore.GREEN}Switch to {self._current_state}{Style.RESET_ALL}"</span><span class="token punctuation">)</span>
        <span class="token keyword">elif</span> event<span class="token punctuation">.</span>key <span class="token operator">==</span> <span class="token string">"0"</span> <span class="token operator">or</span> event<span class="token punctuation">.</span>key <span class="token operator">==</span> <span class="token string">"d"</span><span class="token punctuation">:</span>
            self<span class="token punctuation">.</span>_current_state <span class="token operator">=</span> <span class="token string">"clear_patch"</span>
            <span class="token keyword">print</span><span class="token punctuation">(</span>f<span class="token string">"{Fore.GREEN}Switch to {self._current_state}{Style.RESET_ALL}"</span><span class="token punctuation">)</span>
        <span class="token keyword">elif</span> event<span class="token punctuation">.</span>key <span class="token operator">==</span> <span class="token string">"r"</span><span class="token punctuation">:</span>
            p <span class="token operator">=</span> self<span class="token punctuation">.</span>_current_state
            self<span class="token punctuation">.</span>_current_state <span class="token operator">=</span> <span class="token string">"add_obstacle"</span>
            xs <span class="token operator">=</span> np<span class="token punctuation">.</span>random<span class="token punctuation">.</span>randint<span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">,</span> self<span class="token punctuation">.</span>_mapsize<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">,</span> size<span class="token operator">=</span><span class="token punctuation">(</span>n <span class="token punctuation">:</span><span class="token operator">=</span> self<span class="token punctuation">.</span>_mapsize<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span> <span class="token operator">*</span> self<span class="token punctuation">.</span>_mapsize<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">//</span> <span class="token number">5</span><span class="token punctuation">)</span><span class="token punctuation">)</span>
            ys <span class="token operator">=</span> np<span class="token punctuation">.</span>random<span class="token punctuation">.</span>randint<span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">,</span> self<span class="token punctuation">.</span>_mapsize<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">,</span> size<span class="token operator">=</span>n<span class="token punctuation">)</span>
            self<span class="token punctuation">.</span>add_patch<span class="token punctuation">(</span>xs<span class="token punctuation">,</span> ys<span class="token punctuation">)</span>
            self<span class="token punctuation">.</span>_current_state <span class="token operator">=</span> p
        <span class="token keyword">elif</span> event<span class="token punctuation">.</span>key <span class="token operator">==</span> <span class="token string">"w"</span><span class="token punctuation">:</span>
            files <span class="token operator">=</span> <span class="token punctuation">[</span>i<span class="token punctuation">.</span>stem <span class="token keyword">for</span> i <span class="token keyword">in</span> Path<span class="token punctuation">(</span>__file__<span class="token punctuation">)</span><span class="token punctuation">.</span>resolve<span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">.</span>absolute<span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">.</span>parent<span class="token punctuation">.</span>glob<span class="token punctuation">(</span><span class="token string">"map_*.csv"</span><span class="token punctuation">)</span><span class="token punctuation">]</span>
            <span class="token keyword">if</span> len<span class="token punctuation">(</span>files<span class="token punctuation">)</span> <span class="token operator">></span> <span class="token number">0</span><span class="token punctuation">:</span>
                name <span class="token operator">=</span> f<span class="token string">"map_{int(max([f.split('_')[1] for f in files])) + 1}"</span>
            <span class="token keyword">else</span><span class="token punctuation">:</span>
                name <span class="token operator">=</span> <span class="token string">"map_0"</span>
            self<span class="token punctuation">.</span>pandasfy<span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">.</span>to_csv<span class="token punctuation">(</span>p <span class="token punctuation">:</span><span class="token operator">=</span> Path<span class="token punctuation">(</span>__file__<span class="token punctuation">)</span><span class="token punctuation">.</span>resolve<span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">.</span>parent<span class="token punctuation">.</span>joinpath<span class="token punctuation">(</span>f<span class="token string">"{name}.csv"</span><span class="token punctuation">)</span><span class="token punctuation">)</span>
            <span class="token keyword">print</span><span class="token punctuation">(</span>f<span class="token string">"{Fore.GREEN}Save current Map to {p}{Style.RESET_ALL}"</span><span class="token punctuation">)</span>
        <span class="token keyword">elif</span> event<span class="token punctuation">.</span>key <span class="token operator">==</span> <span class="token string">"v"</span><span class="token punctuation">:</span>
            <span class="token keyword">print</span><span class="token punctuation">(</span>f<span class="token string">"{Fore.GREEN}Start finding goal{self._current_state}{Style.RESET_ALL}"</span><span class="token punctuation">)</span>
            self<span class="token punctuation">.</span>_go_on <span class="token operator">=</span> <span class="token boolean">True</span>
            self<span class="token punctuation">.</span>start<span class="token punctuation">(</span><span class="token punctuation">)</span>
        self<span class="token punctuation">.</span>_update_title<span class="token punctuation">(</span><span class="token punctuation">)</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h3 id="3-算法实现"><a href="#3-算法实现" class="headerlink" title="3. 算法实现"></a>3. 算法实现</h3><p>算法实现由Astar类负责完成，其中由于在计算启发值时可以有多种算法，因此将启发值的计算以静态方法形式嵌入到类中</p>
<p>start方法为完整的A*算法实现，而plot4searching用于在路径规划时动态更新地图</p>
<p>此外OpenList和CloseList分别作为字典的键和值蕴含在came_from和cost_so_far两个字典中，因此不用单独开辟新的数组进行保存</p>
<pre class="line-numbers language-python"><code class="language-python"><span class="token keyword">class</span> <span class="token class-name">Astar</span><span class="token punctuation">(</span>_MapBase<span class="token punctuation">)</span><span class="token punctuation">:</span>
    <span class="token keyword">def</span> <span class="token function">__init__</span><span class="token punctuation">(</span>self<span class="token punctuation">,</span> load_path<span class="token punctuation">:</span> Union<span class="token punctuation">[</span>Path<span class="token punctuation">,</span> None<span class="token punctuation">]</span><span class="token punctuation">,</span> mapsize<span class="token punctuation">:</span> Tuple<span class="token punctuation">[</span>int<span class="token punctuation">,</span> int<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token punctuation">(</span><span class="token number">30</span><span class="token punctuation">,</span> <span class="token number">30</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">:</span>
        super<span class="token punctuation">(</span>Astar<span class="token punctuation">,</span> self<span class="token punctuation">)</span><span class="token punctuation">.</span>__init__<span class="token punctuation">(</span>mapsize<span class="token operator">=</span>mapsize<span class="token punctuation">)</span>

        <span class="token keyword">if</span> load_path <span class="token keyword">is</span> <span class="token operator">not</span> None<span class="token punctuation">:</span>
            <span class="token keyword">print</span><span class="token punctuation">(</span>f<span class="token string">"{Fore.GREEN}Load from {load_path}{Style.RESET_ALL}"</span><span class="token punctuation">)</span>
            self<span class="token punctuation">.</span>depandasfy<span class="token punctuation">(</span>load_path<span class="token punctuation">)</span>
            self<span class="token punctuation">.</span>update<span class="token punctuation">(</span><span class="token punctuation">)</span>
            t <span class="token operator">=</span> np<span class="token punctuation">.</span>where<span class="token punctuation">(</span>self<span class="token punctuation">.</span>map <span class="token operator">==</span> <span class="token operator">-</span><span class="token number">2</span><span class="token punctuation">)</span><span class="token punctuation">,</span> np<span class="token punctuation">.</span>where<span class="token punctuation">(</span>self<span class="token punctuation">.</span>map <span class="token operator">==</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span>
            self<span class="token punctuation">.</span>start_point<span class="token punctuation">:</span> str <span class="token operator">=</span> f<span class="token string">"{t[0][0][0]},{t[0][1][0]}"</span>
            self<span class="token punctuation">.</span>goal_point<span class="token punctuation">:</span> str <span class="token operator">=</span> f<span class="token string">"{t[1][0][0]},{t[1][1][0]}"</span>
            <span class="token comment" spellcheck="true"># open list, but I think frontier is a better name</span>
            <span class="token comment" spellcheck="true"># no need for close list for which has been represented as items of came_from or keys of cost_so_far</span>
            self<span class="token punctuation">.</span>frontier <span class="token operator">=</span> queue<span class="token punctuation">.</span>PriorityQueue<span class="token punctuation">(</span><span class="token punctuation">)</span>
            self<span class="token punctuation">.</span>frontier<span class="token punctuation">.</span>put<span class="token punctuation">(</span><span class="token punctuation">(</span><span class="token number">0</span><span class="token punctuation">,</span> self<span class="token punctuation">.</span>start_point<span class="token punctuation">)</span><span class="token punctuation">)</span>
            self<span class="token punctuation">.</span>came_from<span class="token punctuation">:</span> Dict<span class="token punctuation">[</span>str<span class="token punctuation">,</span> Union<span class="token punctuation">[</span>str<span class="token punctuation">,</span> None<span class="token punctuation">]</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token punctuation">{</span>self<span class="token punctuation">.</span>start_point<span class="token punctuation">:</span> None<span class="token punctuation">}</span>
            self<span class="token punctuation">.</span>cost_so_far<span class="token punctuation">:</span> Dict<span class="token punctuation">[</span>str<span class="token punctuation">,</span> float<span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token punctuation">{</span>self<span class="token punctuation">.</span>start_point<span class="token punctuation">:</span> <span class="token number">0</span><span class="token punctuation">}</span>
            self<span class="token punctuation">.</span>_last<span class="token punctuation">:</span> np<span class="token punctuation">.</span>ndarray <span class="token operator">=</span> None
            plt<span class="token punctuation">.</span>show<span class="token punctuation">(</span><span class="token punctuation">)</span>
        <span class="token keyword">else</span><span class="token punctuation">:</span>
            <span class="token keyword">print</span><span class="token punctuation">(</span>f<span class="token string">"{Fore.GREEN}Start drawing map{Style.RESET_ALL}"</span><span class="token punctuation">)</span>
            plt<span class="token punctuation">.</span>show<span class="token punctuation">(</span><span class="token punctuation">)</span>

    <span class="token keyword">def</span> <span class="token function">start</span><span class="token punctuation">(</span>self<span class="token punctuation">)</span><span class="token punctuation">:</span>
        <span class="token triple-quoted-string string">"""
        Notes:
            A* algorithm implementation
        Returns:
            None
        """</span>
        if_can_find_goal<span class="token punctuation">:</span> bool <span class="token operator">=</span> <span class="token boolean">False</span>
        <span class="token comment" spellcheck="true"># get the closest point</span>
        self<span class="token punctuation">.</span>_current_state <span class="token operator">=</span> <span class="token string">"searching"</span>
        self<span class="token punctuation">.</span>_update_title<span class="token punctuation">(</span><span class="token punctuation">)</span>
        <span class="token keyword">while</span> <span class="token operator">not</span> self<span class="token punctuation">.</span>frontier<span class="token punctuation">.</span>empty<span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">:</span>
            current_p<span class="token punctuation">:</span> str <span class="token operator">=</span> self<span class="token punctuation">.</span>frontier<span class="token punctuation">.</span>get<span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span>

            <span class="token comment" spellcheck="true"># find the goal</span>
            <span class="token keyword">if</span> current_p <span class="token operator">==</span> self<span class="token punctuation">.</span>goal_point<span class="token punctuation">:</span>
                if_can_find_goal <span class="token operator">=</span> <span class="token boolean">True</span>
                <span class="token keyword">break</span>

            next_p<span class="token punctuation">:</span> str
            <span class="token keyword">for</span> next_p <span class="token keyword">in</span> <span class="token punctuation">(</span>n <span class="token punctuation">:</span><span class="token operator">=</span> self<span class="token punctuation">.</span>_get_neighbor<span class="token punctuation">(</span>current_p<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">:</span>
                new_cost <span class="token operator">=</span> self<span class="token punctuation">.</span>cost_so_far<span class="token punctuation">[</span>current_p<span class="token punctuation">]</span> <span class="token operator">+</span> self<span class="token punctuation">.</span>_get_cost<span class="token punctuation">(</span>next_p<span class="token punctuation">,</span> current_p<span class="token punctuation">)</span>
                <span class="token comment" spellcheck="true"># if next point has not been considered / next point in in undiscovered area</span>
                <span class="token comment" spellcheck="true"># or there exists a nearer way to get to next point by passing current point</span>
                <span class="token comment" spellcheck="true"># this also can help preventing going back</span>
                <span class="token keyword">if</span> next_p <span class="token operator">not</span> <span class="token keyword">in</span> self<span class="token punctuation">.</span>cost_so_far<span class="token punctuation">.</span>keys<span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token operator">or</span> new_cost <span class="token operator">&lt;</span> self<span class="token punctuation">.</span>cost_so_far<span class="token punctuation">[</span>next_p<span class="token punctuation">]</span><span class="token punctuation">:</span>
                    self<span class="token punctuation">.</span>cost_so_far<span class="token punctuation">[</span>next_p<span class="token punctuation">]</span> <span class="token operator">=</span> new_cost
                    priority <span class="token operator">=</span> new_cost <span class="token operator">+</span> self<span class="token punctuation">.</span>_get_cost<span class="token punctuation">(</span>next_p<span class="token punctuation">,</span> self<span class="token punctuation">.</span>goal_point<span class="token punctuation">)</span>
                    self<span class="token punctuation">.</span>frontier<span class="token punctuation">.</span>put<span class="token punctuation">(</span><span class="token punctuation">(</span>priority<span class="token punctuation">,</span> next_p<span class="token punctuation">)</span><span class="token punctuation">)</span>
                    current_pp <span class="token operator">=</span> <span class="token punctuation">[</span>int<span class="token punctuation">(</span>i<span class="token punctuation">)</span> <span class="token keyword">for</span> i <span class="token keyword">in</span> current_p<span class="token punctuation">.</span>split<span class="token punctuation">(</span><span class="token string">","</span><span class="token punctuation">)</span><span class="token punctuation">]</span>
                    self<span class="token punctuation">.</span>came_from<span class="token punctuation">[</span>next_p<span class="token punctuation">]</span> <span class="token operator">=</span> f<span class="token string">"{current_pp[0]},{current_pp[1]}"</span>
                    self<span class="token punctuation">.</span>_plot4searching<span class="token punctuation">(</span><span class="token punctuation">)</span>
                    plt<span class="token punctuation">.</span>pause<span class="token punctuation">(</span><span class="token number">0.0001</span><span class="token punctuation">)</span>
                    self<span class="token punctuation">.</span>update<span class="token punctuation">(</span><span class="token punctuation">)</span>
        <span class="token keyword">if</span> <span class="token operator">not</span> if_can_find_goal<span class="token punctuation">:</span>
            <span class="token keyword">print</span><span class="token punctuation">(</span>f<span class="token string">"{Fore.RED}Cannot find the goal in current map{Style.RESET_ALL}"</span><span class="token punctuation">)</span>
            self<span class="token punctuation">.</span>_update_title<span class="token punctuation">(</span><span class="token string">"STOP: cannot find the path!"</span><span class="token punctuation">)</span>
            <span class="token keyword">return</span>
        <span class="token keyword">else</span><span class="token punctuation">:</span>
            <span class="token comment" spellcheck="true"># go back to find the path</span>
            self<span class="token punctuation">.</span>_current_state <span class="token operator">=</span> <span class="token string">"add_goal"</span>
            goal <span class="token operator">=</span> <span class="token punctuation">(</span>int<span class="token punctuation">(</span>i<span class="token punctuation">)</span> <span class="token keyword">for</span> i <span class="token keyword">in</span> self<span class="token punctuation">.</span>goal_point<span class="token punctuation">.</span>split<span class="token punctuation">(</span><span class="token string">","</span><span class="token punctuation">)</span><span class="token punctuation">)</span>
            self<span class="token punctuation">.</span>add_patch<span class="token punctuation">(</span><span class="token operator">*</span>goal<span class="token punctuation">)</span>
            self<span class="token punctuation">.</span>_current_state <span class="token operator">=</span> <span class="token string">"going_back"</span>
            self<span class="token punctuation">.</span>_update_title<span class="token punctuation">(</span><span class="token punctuation">)</span>

            path <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token punctuation">]</span>
            current_p <span class="token operator">=</span> self<span class="token punctuation">.</span>goal_point
            <span class="token keyword">while</span> current_p <span class="token operator">!=</span> self<span class="token punctuation">.</span>start_point<span class="token punctuation">:</span>
                current_p <span class="token operator">=</span> self<span class="token punctuation">.</span>came_from<span class="token punctuation">[</span>current_p<span class="token punctuation">]</span>
                p <span class="token operator">=</span> tuple<span class="token punctuation">(</span>int<span class="token punctuation">(</span>i<span class="token punctuation">)</span> <span class="token keyword">for</span> i <span class="token keyword">in</span> current_p<span class="token punctuation">.</span>split<span class="token punctuation">(</span><span class="token string">","</span><span class="token punctuation">)</span><span class="token punctuation">)</span>
                path<span class="token punctuation">.</span>append<span class="token punctuation">(</span>p<span class="token punctuation">)</span>
                self<span class="token punctuation">.</span>add_patch<span class="token punctuation">(</span><span class="token operator">*</span>p<span class="token punctuation">)</span>
            self<span class="token punctuation">.</span>_current_state <span class="token operator">=</span> <span class="token string">"add_start"</span>
            start <span class="token operator">=</span> <span class="token punctuation">(</span>int<span class="token punctuation">(</span>i<span class="token punctuation">)</span> <span class="token keyword">for</span> i <span class="token keyword">in</span> self<span class="token punctuation">.</span>start_point<span class="token punctuation">.</span>split<span class="token punctuation">(</span><span class="token string">","</span><span class="token punctuation">)</span><span class="token punctuation">)</span>
            self<span class="token punctuation">.</span>add_patch<span class="token punctuation">(</span><span class="token operator">*</span>start<span class="token punctuation">)</span>
        <span class="token keyword">print</span><span class="token punctuation">(</span>f<span class="token string">"{Fore.BLUE}{Style.BRIGHT}Success!{Style.RESET_ALL}"</span><span class="token punctuation">)</span>
        <span class="token keyword">print</span><span class="token punctuation">(</span><span class="token string">"Path:"</span><span class="token punctuation">)</span>
        pprint<span class="token punctuation">.</span>pprint<span class="token punctuation">(</span>path<span class="token punctuation">)</span>
        <span class="token keyword">return</span> path

    <span class="token keyword">def</span> <span class="token function">_get_neighbor</span><span class="token punctuation">(</span>self<span class="token punctuation">,</span> point<span class="token punctuation">:</span> str<span class="token punctuation">)</span><span class="token punctuation">:</span>
        <span class="token keyword">from</span> itertools <span class="token keyword">import</span> product
        x<span class="token punctuation">,</span> y <span class="token operator">=</span> <span class="token punctuation">[</span>int<span class="token punctuation">(</span>i<span class="token punctuation">)</span> <span class="token keyword">for</span> i <span class="token keyword">in</span> point<span class="token punctuation">.</span>split<span class="token punctuation">(</span><span class="token string">","</span><span class="token punctuation">)</span><span class="token punctuation">]</span>
        neighbor <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token punctuation">]</span>
        <span class="token keyword">for</span> i<span class="token punctuation">,</span> j <span class="token keyword">in</span> product<span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token punctuation">[</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">:</span>
            <span class="token keyword">if</span> abs<span class="token punctuation">(</span>i<span class="token punctuation">)</span> <span class="token operator">+</span> abs<span class="token punctuation">(</span>j<span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token number">0</span><span class="token punctuation">:</span>
                <span class="token keyword">continue</span>
            <span class="token keyword">if</span> <span class="token number">0</span> <span class="token operator">&lt;=</span> <span class="token punctuation">(</span>dx <span class="token punctuation">:</span><span class="token operator">=</span> x <span class="token operator">+</span> i<span class="token punctuation">)</span> <span class="token operator">&lt;=</span> self<span class="token punctuation">.</span>_mapsize<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span> <span class="token operator">and</span> <span class="token number">0</span> <span class="token operator">&lt;=</span> <span class="token punctuation">(</span>dy <span class="token punctuation">:</span><span class="token operator">=</span> y <span class="token operator">+</span> j<span class="token punctuation">)</span> <span class="token operator">&lt;=</span> self<span class="token punctuation">.</span>_mapsize<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">and</span> \
                    self<span class="token punctuation">.</span>map<span class="token punctuation">[</span>dx<span class="token punctuation">,</span> dy<span class="token punctuation">]</span> <span class="token operator">!=</span> np<span class="token punctuation">.</span>inf<span class="token punctuation">:</span>
                neighbor<span class="token punctuation">.</span>append<span class="token punctuation">(</span>f<span class="token string">"{dx},{dy}"</span><span class="token punctuation">)</span>
        <span class="token keyword">return</span> neighbor

    <span class="token keyword">def</span> <span class="token function">_get_cost</span><span class="token punctuation">(</span>self<span class="token punctuation">,</span> point1<span class="token punctuation">:</span> str<span class="token punctuation">,</span> point2<span class="token punctuation">:</span> str<span class="token punctuation">)</span><span class="token punctuation">:</span>
        <span class="token comment" spellcheck="true"># x, y = [int(i) for i in point.split(",")]</span>
        <span class="token comment" spellcheck="true"># return self.manhattan_distance(*[int(i) for i in point1.split(",")],</span>
        <span class="token comment" spellcheck="true">#                                *[int(i) for i in point2.split(",")])</span>
        <span class="token keyword">return</span> self<span class="token punctuation">.</span>euler_distance<span class="token punctuation">(</span><span class="token operator">*</span><span class="token punctuation">[</span>int<span class="token punctuation">(</span>i<span class="token punctuation">)</span> <span class="token keyword">for</span> i <span class="token keyword">in</span> point1<span class="token punctuation">.</span>split<span class="token punctuation">(</span><span class="token string">","</span><span class="token punctuation">)</span><span class="token punctuation">]</span><span class="token punctuation">,</span>
                                   <span class="token operator">*</span><span class="token punctuation">[</span>int<span class="token punctuation">(</span>i<span class="token punctuation">)</span> <span class="token keyword">for</span> i <span class="token keyword">in</span> point2<span class="token punctuation">.</span>split<span class="token punctuation">(</span><span class="token string">","</span><span class="token punctuation">)</span><span class="token punctuation">]</span><span class="token punctuation">)</span>

    <span class="token keyword">def</span> <span class="token function">_plot4searching</span><span class="token punctuation">(</span>self<span class="token punctuation">)</span><span class="token punctuation">:</span>
        <span class="token triple-quoted-string string">"""Codes for plotting"""</span>
        <span class="token comment" spellcheck="true"># update current map</span>
        <span class="token comment" spellcheck="true"># explore area</span>
        explored_ps <span class="token operator">=</span> <span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">)</span>
        <span class="token keyword">for</span> p<span class="token punctuation">,</span> parent <span class="token keyword">in</span> self<span class="token punctuation">.</span>came_from<span class="token punctuation">.</span>items<span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">:</span>
            pp <span class="token operator">=</span> <span class="token punctuation">[</span>int<span class="token punctuation">(</span>i<span class="token punctuation">)</span> <span class="token keyword">for</span> i <span class="token keyword">in</span> p<span class="token punctuation">.</span>split<span class="token punctuation">(</span><span class="token string">","</span><span class="token punctuation">)</span><span class="token punctuation">]</span>
            <span class="token keyword">if</span> parent <span class="token keyword">is</span> <span class="token operator">not</span> None<span class="token punctuation">:</span>
                explored_ps<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">.</span>append<span class="token punctuation">(</span>pp<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">)</span>
                explored_ps<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">.</span>append<span class="token punctuation">(</span>pp<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">)</span>
        self<span class="token punctuation">.</span>map<span class="token punctuation">[</span>np<span class="token punctuation">.</span>array<span class="token punctuation">(</span>explored_ps<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">,</span> np<span class="token punctuation">.</span>array<span class="token punctuation">(</span><span class="token punctuation">(</span>explored_ps<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">1</span>

        <span class="token comment" spellcheck="true"># frontier</span>
        frontier_ps <span class="token operator">=</span> <span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">)</span>
        t <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token punctuation">]</span>
        <span class="token keyword">while</span> <span class="token operator">not</span> self<span class="token punctuation">.</span>frontier<span class="token punctuation">.</span>empty<span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">:</span>
            t<span class="token punctuation">.</span>append<span class="token punctuation">(</span>self<span class="token punctuation">.</span>frontier<span class="token punctuation">.</span>get<span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">)</span>
        <span class="token keyword">for</span> i <span class="token keyword">in</span> t<span class="token punctuation">:</span>
            self<span class="token punctuation">.</span>frontier<span class="token punctuation">.</span>put<span class="token punctuation">(</span>i<span class="token punctuation">)</span>
        <span class="token keyword">for</span> tt <span class="token keyword">in</span> t<span class="token punctuation">:</span>
            <span class="token comment" spellcheck="true"># frontier_ps.append(t.get()[1])</span>
            p <span class="token operator">=</span> <span class="token punctuation">[</span>int<span class="token punctuation">(</span>i<span class="token punctuation">)</span> <span class="token keyword">for</span> i <span class="token keyword">in</span> tt<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">.</span>split<span class="token punctuation">(</span><span class="token string">","</span><span class="token punctuation">)</span><span class="token punctuation">]</span>
            frontier_ps<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">.</span>append<span class="token punctuation">(</span>p<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">)</span>
            frontier_ps<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">.</span>append<span class="token punctuation">(</span>p<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">)</span>
        <span class="token comment" spellcheck="true"># simply deepcopy locked object will raise an error</span>
        <span class="token comment" spellcheck="true"># t = copy.deepcopy(self.frontier)</span>
        self<span class="token punctuation">.</span>map<span class="token punctuation">[</span>np<span class="token punctuation">.</span>array<span class="token punctuation">(</span>frontier_ps<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">,</span> np<span class="token punctuation">.</span>array<span class="token punctuation">(</span>frontier_ps<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token number">2</span>

        <span class="token comment" spellcheck="true"># find difference</span>
        <span class="token keyword">if</span> self<span class="token punctuation">.</span>_last <span class="token keyword">is</span> None<span class="token punctuation">:</span>
            update_explored <span class="token operator">=</span> list<span class="token punctuation">(</span>zip<span class="token punctuation">(</span><span class="token operator">*</span>np<span class="token punctuation">.</span>where<span class="token punctuation">(</span>self<span class="token punctuation">.</span>map <span class="token operator">==</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">)</span>
            update_frontier <span class="token operator">=</span> list<span class="token punctuation">(</span>zip<span class="token punctuation">(</span><span class="token operator">*</span>np<span class="token punctuation">.</span>where<span class="token punctuation">(</span>self<span class="token punctuation">.</span>map <span class="token operator">==</span> <span class="token number">2</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">)</span>
            <span class="token comment" spellcheck="true"># update_frontier = [(i,j) for i, j in zip(*update_frontier)]</span>
        <span class="token keyword">else</span><span class="token punctuation">:</span>
            last_explored <span class="token operator">=</span> list<span class="token punctuation">(</span>zip<span class="token punctuation">(</span><span class="token operator">*</span>np<span class="token punctuation">.</span>where<span class="token punctuation">(</span>self<span class="token punctuation">.</span>_last <span class="token operator">==</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">)</span>
            last_frontier <span class="token operator">=</span> list<span class="token punctuation">(</span>zip<span class="token punctuation">(</span><span class="token operator">*</span>np<span class="token punctuation">.</span>where<span class="token punctuation">(</span>self<span class="token punctuation">.</span>_last <span class="token operator">==</span> <span class="token number">2</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">)</span>
            current_explored <span class="token operator">=</span> list<span class="token punctuation">(</span>zip<span class="token punctuation">(</span><span class="token operator">*</span>np<span class="token punctuation">.</span>where<span class="token punctuation">(</span>self<span class="token punctuation">.</span>map <span class="token operator">==</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">)</span>
            current_frontier <span class="token operator">=</span> list<span class="token punctuation">(</span>zip<span class="token punctuation">(</span><span class="token operator">*</span>np<span class="token punctuation">.</span>where<span class="token punctuation">(</span>self<span class="token punctuation">.</span>map <span class="token operator">==</span> <span class="token number">2</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">)</span>
            update_explored <span class="token operator">=</span> list<span class="token punctuation">(</span>set<span class="token punctuation">(</span>current_explored<span class="token punctuation">)</span> <span class="token operator">-</span> set<span class="token punctuation">(</span>last_explored<span class="token punctuation">)</span><span class="token punctuation">)</span>
            update_frontier <span class="token operator">=</span> list<span class="token punctuation">(</span>set<span class="token punctuation">(</span>current_frontier<span class="token punctuation">)</span> <span class="token operator">-</span> set<span class="token punctuation">(</span>last_frontier<span class="token punctuation">)</span><span class="token punctuation">)</span>
        self<span class="token punctuation">.</span>_last <span class="token operator">=</span> self<span class="token punctuation">.</span>map<span class="token punctuation">.</span>copy<span class="token punctuation">(</span><span class="token punctuation">)</span>
        <span class="token comment" spellcheck="true"># draw explored area</span>
        <span class="token keyword">if</span> len<span class="token punctuation">(</span>update_explored<span class="token punctuation">)</span> <span class="token operator">></span> <span class="token number">0</span><span class="token punctuation">:</span>
            self<span class="token punctuation">.</span>add_patch<span class="token punctuation">(</span>np<span class="token punctuation">.</span>array<span class="token punctuation">(</span><span class="token punctuation">[</span>i<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span> <span class="token keyword">for</span> i <span class="token keyword">in</span> update_explored<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">,</span> np<span class="token punctuation">.</span>array<span class="token punctuation">(</span><span class="token punctuation">[</span>i<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span> <span class="token keyword">for</span> i <span class="token keyword">in</span> update_explored<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">,</span>
                           patches<span class="token operator">=</span><span class="token string">"explored"</span><span class="token punctuation">)</span>
        <span class="token comment" spellcheck="true"># draw frontier</span>
        <span class="token keyword">if</span> len<span class="token punctuation">(</span>update_frontier<span class="token punctuation">)</span> <span class="token operator">></span> <span class="token number">0</span><span class="token punctuation">:</span>
            self<span class="token punctuation">.</span>add_patch<span class="token punctuation">(</span>np<span class="token punctuation">.</span>array<span class="token punctuation">(</span><span class="token punctuation">[</span>i<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span> <span class="token keyword">for</span> i <span class="token keyword">in</span> update_frontier<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">,</span> np<span class="token punctuation">.</span>array<span class="token punctuation">(</span><span class="token punctuation">[</span>i<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span> <span class="token keyword">for</span> i <span class="token keyword">in</span> update_frontier<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">,</span>
                           patches<span class="token operator">=</span><span class="token string">"frontier"</span><span class="token punctuation">)</span>

    @staticmethod
    <span class="token keyword">def</span> <span class="token function">manhattan_distance</span><span class="token punctuation">(</span>x1<span class="token punctuation">,</span> y1<span class="token punctuation">,</span> x2<span class="token punctuation">,</span> y2<span class="token punctuation">)</span><span class="token punctuation">:</span>
        <span class="token keyword">return</span> abs<span class="token punctuation">(</span>x2 <span class="token operator">-</span> x1<span class="token punctuation">)</span> <span class="token operator">+</span> abs<span class="token punctuation">(</span>y2 <span class="token operator">-</span> y1<span class="token punctuation">)</span>

    @staticmethod
    <span class="token keyword">def</span> <span class="token function">euler_distance</span><span class="token punctuation">(</span>x1<span class="token punctuation">,</span> y1<span class="token punctuation">,</span> x2<span class="token punctuation">,</span> y2<span class="token punctuation">)</span><span class="token punctuation">:</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>d <span class="token punctuation">:</span><span class="token operator">=</span> abs<span class="token punctuation">(</span>x2 <span class="token operator">-</span> x1<span class="token punctuation">)</span> <span class="token operator">+</span> abs<span class="token punctuation">(</span>y2 <span class="token operator">-</span> y1<span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token operator">==</span> <span class="token number">1</span><span class="token punctuation">:</span>
            <span class="token keyword">return</span> <span class="token number">1</span>
        <span class="token keyword">elif</span> d <span class="token operator">==</span> <span class="token number">2</span><span class="token punctuation">:</span>
            <span class="token keyword">return</span> <span class="token number">1.4</span>
        <span class="token keyword">else</span><span class="token punctuation">:</span>
            <span class="token keyword">return</span> round<span class="token punctuation">(</span>np<span class="token punctuation">.</span>sqrt<span class="token punctuation">(</span><span class="token punctuation">(</span>x2 <span class="token operator">-</span> x1<span class="token punctuation">)</span> <span class="token operator">**</span> <span class="token number">2</span> <span class="token operator">+</span> <span class="token punctuation">(</span>y2 <span class="token operator">-</span> y1<span class="token punctuation">)</span> <span class="token operator">**</span> <span class="token number">2</span><span class="token punctuation">)</span><span class="token punctuation">,</span> ndigits<span class="token operator">=</span><span class="token number">2</span><span class="token punctuation">)</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h3 id="4-命令行参数解析"><a href="#4-命令行参数解析" class="headerlink" title="4. 命令行参数解析"></a>4. 命令行参数解析</h3><p>命令行参数解析由parse_arg函数负责完成，并返回Namespace对象</p>
<pre class="line-numbers language-python"><code class="language-python"><span class="token keyword">def</span> <span class="token function">parse_arg</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">:</span>
    parer <span class="token operator">=</span> argparse<span class="token punctuation">.</span>ArgumentParser<span class="token punctuation">(</span>
        description<span class="token operator">=</span>f<span class="token string">"{Fore.GREEN}{Style.BRIGHT}A* Algorithm, animated with matplotlib{Style.RESET_ALL}. "</span>
                    f<span class="token string">"Author: {Fore.YELLOW}Jack Wang{Fore.RESET}. "</span>
                    f<span class="token string">"Date: {Fore.YELLOW}2021-12-15{Style.RESET_ALL}."</span>
                    <span class="token string">"This script provides A* algorithm illustration with the help of matplotlib\n"</span>
                    f<span class="token string">"You can use this script either by {Fore.GREEN}command-line interface{Fore.RESET} "</span>
                    f<span class="token string">"or {Fore.GREEN}python code interface{Fore.RESET}."</span>
                    <span class="token string">"To use this script with command-line interface, call this script with -h option. "</span>
                    <span class="token string">"To use this script in python code, "</span>
                    <span class="token string">"simply calling Astar class to create an Astar object, then everything will be done. "</span>
                    <span class="token string">"If load_path argument of Astar class are not specified (i.e. load_path=None), "</span>
                    <span class="token string">"this program will create a blank"</span>
                    <span class="token string">"map for you, else loading an existing map."</span>
                    <span class="token string">"\n\n"</span>
                    <span class="token string">"In the matplotlib GUI, press 1 to add obstacle, 2 to add goal, 3 to add start, w to save map, "</span>
                    <span class="token string">"r to random generate obstacles, d to delete an grid and v to start path planning. "</span>
                    f<span class="token string">"{Fore.YELLOW}Note: when call with -c, you can not press v to start path planning, -c is only "</span>
                    f<span class="token string">"for drawing map. {Style.RESET_ALL}"</span><span class="token punctuation">)</span>
    parer<span class="token punctuation">.</span>add_argument<span class="token punctuation">(</span><span class="token string">"-o"</span><span class="token punctuation">,</span> dest<span class="token operator">=</span><span class="token string">"ok"</span><span class="token punctuation">,</span> action<span class="token operator">=</span><span class="token string">"store_true"</span><span class="token punctuation">,</span> help<span class="token operator">=</span><span class="token string">"must be added when calling the scripts to let me "</span>
                                                                  <span class="token string">"know you understand how to use this program"</span><span class="token punctuation">)</span>
    parer<span class="token punctuation">.</span>add_argument<span class="token punctuation">(</span><span class="token string">"-c"</span><span class="token punctuation">,</span> dest<span class="token operator">=</span><span class="token string">"gen_map"</span><span class="token punctuation">,</span> action<span class="token operator">=</span><span class="token string">"store_true"</span><span class="token punctuation">,</span> help<span class="token operator">=</span><span class="token string">"create a new map"</span><span class="token punctuation">)</span>
    parer<span class="token punctuation">.</span>add_argument<span class="token punctuation">(</span><span class="token string">"-l"</span><span class="token punctuation">,</span> dest<span class="token operator">=</span><span class="token string">"load_num"</span><span class="token punctuation">,</span> type<span class="token operator">=</span>int<span class="token punctuation">,</span> default<span class="token operator">=</span><span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">,</span> help<span class="token operator">=</span><span class="token string">"load a existing map"</span><span class="token punctuation">)</span>
    <span class="token keyword">return</span> parer<span class="token punctuation">.</span>parse_args<span class="token punctuation">(</span><span class="token punctuation">)</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>
<h3 id="5-主程序"><a href="#5-主程序" class="headerlink" title="5. 主程序"></a>5. 主程序</h3><p>主程序中若不提供加载的地图路径则默认打开新的地图用于地图绘制</p>
<pre class="line-numbers language-python"><code class="language-python"><span class="token keyword">def</span> <span class="token function">main</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">:</span>
    args <span class="token operator">=</span> parse_arg<span class="token punctuation">(</span><span class="token punctuation">)</span>
    <span class="token keyword">if</span> <span class="token operator">not</span> args<span class="token punctuation">.</span>ok<span class="token punctuation">:</span>
        <span class="token keyword">print</span><span class="token punctuation">(</span>f<span class="token string">"{Fore.RED}Please read the help info with -h option the rerun the scripts with -o option{Fore.RESET}"</span><span class="token punctuation">)</span>
        <span class="token keyword">return</span>
    <span class="token keyword">if</span> args<span class="token punctuation">.</span>gen_map<span class="token punctuation">:</span>
        Astar<span class="token punctuation">(</span>load_path<span class="token operator">=</span>None<span class="token punctuation">)</span>
        <span class="token keyword">return</span>
    <span class="token keyword">if</span> args<span class="token punctuation">.</span>load_num <span class="token operator">!=</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">:</span>
        Astar<span class="token punctuation">(</span>load_path<span class="token operator">=</span>Path<span class="token punctuation">(</span>__file__<span class="token punctuation">)</span><span class="token punctuation">.</span>resolve<span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">.</span>parent<span class="token punctuation">.</span>joinpath<span class="token punctuation">(</span>f<span class="token string">"map_{args.load_num}.csv"</span><span class="token punctuation">)</span><span class="token punctuation">)</span>


<span class="token keyword">if</span> __name__ <span class="token operator">==</span> <span class="token string">"__main__"</span><span class="token punctuation">:</span>
    <span class="token comment" spellcheck="true"># a = Astar(load_path=Path("./map_4.csv"))</span>
    <span class="token comment" spellcheck="true"># a = Astar(load_path=Path(__file__).resolve().parent.joinpath("./map_1.csv"))</span>
    main<span class="token punctuation">(</span><span class="token punctuation">)</span>
<span aria-hidden="true" class="line-numbers-rows"><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span><span></span></span></code></pre>

                
            </div>
            <hr/>

            

    <div class="reprint" id="reprint-statement">
        
            <div class="reprint__author">
                <span class="reprint-meta" style="font-weight: bold;">
                    <i class="fas fa-user">
                        文章作者:
                    </i>
                </span>
                <span class="reprint-info">
                    <a href="/about" rel="external nofollow noreferrer">Jack Wang</a>
                </span>
            </div>
            <div class="reprint__type">
                <span class="reprint-meta" style="font-weight: bold;">
                    <i class="fas fa-link">
                        文章链接:
                    </i>
                </span>
                <span class="reprint-info">
                    <a href="https://jackwang0107.github.io/2021/12/22/a-suan-fa-python-shi-xian/">https://jackwang0107.github.io/2021/12/22/a-suan-fa-python-shi-xian/</a>
                </span>
            </div>
            <div class="reprint__notice">
                <span class="reprint-meta" style="font-weight: bold;">
                    <i class="fas fa-copyright">
                        版权声明:
                    </i>
                </span>
                <span class="reprint-info">
                    本博客所有文章除特別声明外，均采用
                    <a href="https://creativecommons.org/licenses/by/4.0/deed.zh" rel="external nofollow noreferrer" target="_blank">CC BY 4.0</a>
                    许可协议。转载请注明来源
                    <a href="/about" target="_blank">Jack Wang</a>
                    !
                </span>
            </div>
        
    </div>

    <script async defer>
      document.addEventListener("copy", function (e) {
        let toastHTML = '<span>复制成功，请遵循本文的转载规则</span><button class="btn-flat toast-action" onclick="navToReprintStatement()" style="font-size: smaller">查看</a>';
        M.toast({html: toastHTML})
      });

      function navToReprintStatement() {
        $("html, body").animate({scrollTop: $("#reprint-statement").offset().top - 80}, 800);
      }
    </script>



            <div class="tag_share" style="display: block;">
                <div class="post-meta__tag-list" style="display: inline-block;">
                    
                        <div class="article-tag">
                            
                                <a href="/tags/DataStructure/">
                                    <span class="chip bg-color">DataStructure</span>
                                </a>
                            
                                <a href="/tags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/">
                                    <span class="chip bg-color">数据结构</span>
                                </a>
                            
                                <a href="/tags/A/">
                                    <span class="chip bg-color">A*</span>
                                </a>
                            
                                <a href="/tags/PathPlanning/">
                                    <span class="chip bg-color">PathPlanning</span>
                                </a>
                            
                                <a href="/tags/Python/">
                                    <span class="chip bg-color">Python</span>
                                </a>
                            
                                <a href="/tags/Matplotlib/">
                                    <span class="chip bg-color">Matplotlib</span>
                                </a>
                            
                                <a href="/tags/GUI/">
                                    <span class="chip bg-color">GUI</span>
                                </a>
                            
                        </div>
                    
                </div>
                <div class="post_share" style="zoom: 80%; width: fit-content; display: inline-block; float: right; margin: -0.15rem 0;">
                    <link rel="stylesheet" type="text/css" href="/libs/share/css/share.min.css">
<div id="article-share">

    
    <div class="social-share" data-sites="twitter,facebook,google,qq,qzone,wechat,weibo,douban,linkedin" data-wechat-qrcode-helper="<p>微信扫一扫即可分享！</p>"></div>
    <script src="/libs/share/js/social-share.min.js"></script>
    

    

</div>

                </div>
            </div>
            
                <style>
    #reward {
        margin: 40px 0;
        text-align: center;
    }

    #reward .reward-link {
        font-size: 1.4rem;
        line-height: 38px;
    }

    #reward .btn-floating:hover {
        box-shadow: 0 6px 12px rgba(0, 0, 0, 0.2), 0 5px 15px rgba(0, 0, 0, 0.2);
    }

    #rewardModal {
        width: 320px;
        height: 350px;
    }

    #rewardModal .reward-title {
        margin: 15px auto;
        padding-bottom: 5px;
    }

    #rewardModal .modal-content {
        padding: 10px;
    }

    #rewardModal .close {
        position: absolute;
        right: 15px;
        top: 15px;
        color: rgba(0, 0, 0, 0.5);
        font-size: 1.3rem;
        line-height: 20px;
        cursor: pointer;
    }

    #rewardModal .close:hover {
        color: #ef5350;
        transform: scale(1.3);
        -moz-transform:scale(1.3);
        -webkit-transform:scale(1.3);
        -o-transform:scale(1.3);
    }

    #rewardModal .reward-tabs {
        margin: 0 auto;
        width: 210px;
    }

    .reward-tabs .tabs {
        height: 38px;
        margin: 10px auto;
        padding-left: 0;
    }

    .reward-content ul {
        padding-left: 0 !important;
    }

    .reward-tabs .tabs .tab {
        height: 38px;
        line-height: 38px;
    }

    .reward-tabs .tab a {
        color: #fff;
        background-color: #ccc;
    }

    .reward-tabs .tab a:hover {
        background-color: #ccc;
        color: #fff;
    }

    .reward-tabs .wechat-tab .active {
        color: #fff !important;
        background-color: #22AB38 !important;
    }

    .reward-tabs .alipay-tab .active {
        color: #fff !important;
        background-color: #019FE8 !important;
    }

    .reward-tabs .reward-img {
        width: 210px;
        height: 210px;
    }
</style>

<div id="reward">
    <a href="#rewardModal" class="reward-link modal-trigger btn-floating btn-medium waves-effect waves-light red">赏</a>

    <!-- Modal Structure -->
    <div id="rewardModal" class="modal">
        <div class="modal-content">
            <a class="close modal-close"><i class="fas fa-times"></i></a>
            <h4 class="reward-title">你的赏识是我前进的动力</h4>
            <div class="reward-content">
                <div class="reward-tabs">
                    <ul class="tabs row">
                        <li class="tab col s6 alipay-tab waves-effect waves-light"><a href="#alipay">支付宝</a></li>
                        <li class="tab col s6 wechat-tab waves-effect waves-light"><a href="#wechat">微 信</a></li>
                    </ul>
                    <div id="alipay">
                        <img src="/medias/reward/alipay.png" class="reward-img" alt="支付宝打赏二维码">
                    </div>
                    <div id="wechat">
                        <img src="/medias/reward/wechat.jpg" class="reward-img" alt="微信打赏二维码">
                    </div>
                </div>
            </div>
        </div>
    </div>
</div>

<script>
    $(function () {
        $('.tabs').tabs();
    });
</script>

            
        </div>
    </div>

    

    

    

    

    

    

    

    

    

<article id="prenext-posts" class="prev-next articles">
    <div class="row article-row">
        
        <div class="article col s12 m6" data-aos="fade-up">
            <div class="article-badge left-badge text-color">
                <i class="fas fa-chevron-left"></i>&nbsp;上一篇</div>
            <div class="card">
                <a href="/2021/12/28/ubuntu-xia-qq-he-wei-xin-jie-jue-fang-fa/">
                    <div class="card-image">
                        
                        <img src="https://jack-1307599355.cos.ap-shanghai.myqcloud.com/img/image-20211229230820817.png" class="responsive-img" alt="Ubuntu下QQ和微信解决方法">
                        
                        <span class="card-title">Ubuntu下QQ和微信解决方法</span>
                    </div>
                </a>
                <div class="card-content article-content">
                    <div class="summary block-with-text">
                        
                            QQ和微信作为国民级的应用，无论是聊天还是传输文件都非常的方便。本文介绍了如何在类似Ubuntu这类的Linux平台上使用微信和QQ。
                        
                    </div>
                    <div class="publish-info">
                        <span class="publish-date">
                            <i class="far fa-clock fa-fw icon-date"></i>2021-12-28
                        </span>
                        <span class="publish-author">
                            
                            <i class="fas fa-bookmark fa-fw icon-category"></i>
                            
                            <a href="/categories/Linux%E5%AE%9E%E7%94%A8%E6%8A%80%E5%B7%A7/" class="post-category">
                                    Linux实用技巧
                                </a>
                            
                            
                        </span>
                    </div>
                </div>
                
                <div class="card-action article-tags">
                    
                    <a href="/tags/Linux/">
                        <span class="chip bg-color">Linux</span>
                    </a>
                    
                    <a href="/tags/Ubuntu/">
                        <span class="chip bg-color">Ubuntu</span>
                    </a>
                    
                    <a href="/tags/QQ/">
                        <span class="chip bg-color">QQ</span>
                    </a>
                    
                    <a href="/tags/%E5%BE%AE%E4%BF%A1/">
                        <span class="chip bg-color">微信</span>
                    </a>
                    
                    <a href="/tags/Wechat/">
                        <span class="chip bg-color">Wechat</span>
                    </a>
                    
                    <a href="/tags/Virtualbox/">
                        <span class="chip bg-color">Virtualbox</span>
                    </a>
                    
                </div>
                
            </div>
        </div>
        
        
        <div class="article col s12 m6" data-aos="fade-up">
            <div class="article-badge right-badge text-color">
                下一篇&nbsp;<i class="fas fa-chevron-right"></i>
            </div>
            <div class="card">
                <a href="/2021/12/21/ha-fu-man-ya-suo-suan-fa-python-shi-xian/">
                    <div class="card-image">
                        
                        <img src="https://jack-1307599355.cos.ap-shanghai.myqcloud.com/img/image-20211222111040507.png" class="responsive-img" alt="哈夫曼（Huffman Encoding）压缩算法-Python实现">
                        
                        <span class="card-title">哈夫曼（Huffman Encoding）压缩算法-Python实现</span>
                    </div>
                </a>
                <div class="card-content article-content">
                    <div class="summary block-with-text">
                        
                            本文主要提供了Python版本的哈夫曼压缩算法实现，并在此基础上提供了命令行和基于Qt的GUI用户界面（User Interface）
                        
                    </div>
                    <div class="publish-info">
                            <span class="publish-date">
                                <i class="far fa-clock fa-fw icon-date"></i>2021-12-21
                            </span>
                        <span class="publish-author">
                            
                            <i class="fas fa-bookmark fa-fw icon-category"></i>
                            
                            <a href="/categories/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/" class="post-category">
                                    数据结构与算法
                                </a>
                            
                            
                        </span>
                    </div>
                </div>
                
                <div class="card-action article-tags">
                    
                    <a href="/tags/DataStructure/">
                        <span class="chip bg-color">DataStructure</span>
                    </a>
                    
                    <a href="/tags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/">
                        <span class="chip bg-color">数据结构</span>
                    </a>
                    
                    <a href="/tags/Python/">
                        <span class="chip bg-color">Python</span>
                    </a>
                    
                    <a href="/tags/GUI/">
                        <span class="chip bg-color">GUI</span>
                    </a>
                    
                    <a href="/tags/PyQt/">
                        <span class="chip bg-color">PyQt</span>
                    </a>
                    
                    <a href="/tags/HuffmanEncode/">
                        <span class="chip bg-color">HuffmanEncode</span>
                    </a>
                    
                    <a href="/tags/HuffmanAlgorithm/">
                        <span class="chip bg-color">HuffmanAlgorithm</span>
                    </a>
                    
                </div>
                
            </div>
        </div>
        
    </div>
</article>

</div>


<script>
    $('#articleContent').on('copy', function (e) {
        // IE8 or earlier browser is 'undefined'
        if (typeof window.getSelection === 'undefined') return;

        var selection = window.getSelection();
        // if the selection is short let's not annoy our users.
        if (('' + selection).length < Number.parseInt('120')) {
            return;
        }

        // create a div outside of the visible area and fill it with the selected text.
        var bodyElement = document.getElementsByTagName('body')[0];
        var newdiv = document.createElement('div');
        newdiv.style.position = 'absolute';
        newdiv.style.left = '-99999px';
        bodyElement.appendChild(newdiv);
        newdiv.appendChild(selection.getRangeAt(0).cloneContents());

        // we need a <pre> tag workaround.
        // otherwise the text inside "pre" loses all the line breaks!
        if (selection.getRangeAt(0).commonAncestorContainer.nodeName === 'PRE' || selection.getRangeAt(0).commonAncestorContainer.nodeName === 'CODE') {
            newdiv.innerHTML = "<pre>" + newdiv.innerHTML + "</pre>";
        }

        var url = document.location.href;
        newdiv.innerHTML += '<br />'
            + '来源: JackWang&#39;s Blog<br />'
            + '文章作者: Jack Wang<br />'
            + '文章链接: <a href="' + url + '">' + url + '</a><br />'
            + '本文章著作权归作者所有，任何形式的转载都请注明出处。';

        selection.selectAllChildren(newdiv);
        window.setTimeout(function () {bodyElement.removeChild(newdiv);}, 200);
    });
</script>


<!-- 代码块功能依赖 -->
<script type="text/javascript" src="/libs/codeBlock/codeBlockFuction.js"></script>

<!-- 代码语言 -->

<script type="text/javascript" src="/libs/codeBlock/codeLang.js"></script>


<!-- 代码块复制 -->

<script type="text/javascript" src="/libs/codeBlock/codeCopy.js"></script>


<!-- 代码块收缩 -->

<script type="text/javascript" src="/libs/codeBlock/codeShrink.js"></script>


    </div>
    <div id="toc-aside" class="expanded col l3 hide-on-med-and-down">
        <div class="toc-widget card" style="background-color: white;">
            <div class="toc-title"><i class="far fa-list-alt"></i>&nbsp;&nbsp;目录</div>
            <div id="toc-content"></div>
        </div>
    </div>
</div>

<!-- TOC 悬浮按钮. -->

<div id="floating-toc-btn" class="hide-on-med-and-down">
    <a class="btn-floating btn-large bg-color">
        <i class="fas fa-list-ul"></i>
    </a>
</div>


<script src="/libs/tocbot/tocbot.min.js"></script>
<script>
    $(function () {
        tocbot.init({
            tocSelector: '#toc-content',
            contentSelector: '#articleContent',
            headingsOffset: -($(window).height() * 0.4 - 45),
            collapseDepth: Number('2'),
            headingSelector: 'h1, h2, h3, h4, h5, h6'
        });

        // modify the toc link href to support Chinese.
        let i = 0;
        let tocHeading = 'toc-heading-';
        $('#toc-content a').each(function () {
            $(this).attr('href', '#' + tocHeading + (++i));
        });

        // modify the heading title id to support Chinese.
        i = 0;
        $('#articleContent').children('h1, h2, h3, h4, h5, h6').each(function () {
            $(this).attr('id', tocHeading + (++i));
        });

        // Set scroll toc fixed.
        let tocHeight = parseInt($(window).height() * 0.4 - 64);
        let $tocWidget = $('.toc-widget');
        $(window).scroll(function () {
            let scroll = $(window).scrollTop();
            /* add post toc fixed. */
            if (scroll > tocHeight) {
                $tocWidget.addClass('toc-fixed');
            } else {
                $tocWidget.removeClass('toc-fixed');
            }
        });

        
        /* 修复文章卡片 div 的宽度. */
        let fixPostCardWidth = function (srcId, targetId) {
            let srcDiv = $('#' + srcId);
            if (srcDiv.length === 0) {
                return;
            }

            let w = srcDiv.width();
            if (w >= 450) {
                w = w + 21;
            } else if (w >= 350 && w < 450) {
                w = w + 18;
            } else if (w >= 300 && w < 350) {
                w = w + 16;
            } else {
                w = w + 14;
            }
            $('#' + targetId).width(w);
        };

        // 切换TOC目录展开收缩的相关操作.
        const expandedClass = 'expanded';
        let $tocAside = $('#toc-aside');
        let $mainContent = $('#main-content');
        $('#floating-toc-btn .btn-floating').click(function () {
            if ($tocAside.hasClass(expandedClass)) {
                $tocAside.removeClass(expandedClass).hide();
                $mainContent.removeClass('l9');
            } else {
                $tocAside.addClass(expandedClass).show();
                $mainContent.addClass('l9');
            }
            fixPostCardWidth('artDetail', 'prenext-posts');
        });
        
    });
</script>

    

</main>




    <footer class="page-footer bg-color">
    

    <div class="container row center-align"
         style="margin-bottom: 15px !important;">
        <div class="col s12 m8 l8 copy-right">
            Copyright&nbsp;&copy;
            
                <span id="year">2021-2023</span>
            
            <a href="/about" target="_blank">Jack Wang</a>
            <!-- |&nbsp;Powered by&nbsp;<a href="https://hexo.io/" target="_blank">Hexo</a> -->
            <!-- |&nbsp;Theme&nbsp;<a href="https://github.com/blinkfox/hexo-theme-matery" target="_blank">Matery</a> -->
            <br>
            
                &nbsp;<i class="fas fa-chart-area"></i>&nbsp;站点总字数:&nbsp;<span
                        class="white-color">603.8k</span>
            
            
            
                
            
            
                <span id="busuanzi_container_site_pv">
                &nbsp;|&nbsp;<i class="far fa-eye"></i>&nbsp;总访问量:&nbsp;
                    <span id="busuanzi_value_site_pv" class="white-color"></span>
            </span>
            
            
                <span id="busuanzi_container_site_uv">
                &nbsp;|&nbsp;<i class="fas fa-users"></i>&nbsp;总访问人数:&nbsp;
                    <span id="busuanzi_value_site_uv" class="white-color"></span>
            </span>
            
            <br>

            <!-- 运行天数提醒. -->
            
                <span id="sitetime"> Loading ...</span>
                <script>
                    var calcSiteTime = function () {
                        var seconds = 1000;
                        var minutes = seconds * 60;
                        var hours = minutes * 60;
                        var days = hours * 24;
                        var years = days * 365;
                        var today = new Date();
                        var startYear = "2021";
                        var startMonth = "11";
                        var startDate = "12";
                        var startHour = "0";
                        var startMinute = "0";
                        var startSecond = "0";
                        var todayYear = today.getFullYear();
                        var todayMonth = today.getMonth() + 1;
                        var todayDate = today.getDate();
                        var todayHour = today.getHours();
                        var todayMinute = today.getMinutes();
                        var todaySecond = today.getSeconds();
                        var t1 = Date.UTC(startYear, startMonth, startDate, startHour, startMinute, startSecond);
                        var t2 = Date.UTC(todayYear, todayMonth, todayDate, todayHour, todayMinute, todaySecond);
                        var diff = t2 - t1;
                        var diffYears = Math.floor(diff / years);
                        var diffDays = Math.floor((diff / days) - diffYears * 365);

                        // 区分是否有年份.
                        var language = 'zh-CN';
                        if (startYear === String(todayYear)) {
                            document.getElementById("year").innerHTML = todayYear;
                            var daysTip = 'This site has been running for ' + diffDays + ' days';
                            if (language === 'zh-CN') {
                                daysTip = '本站已运行 ' + diffDays + ' 天';
                            } else if (language === 'zh-HK') {
                                daysTip = '本站已運行 ' + diffDays + ' 天';
                            }
                            document.getElementById("sitetime").innerHTML = daysTip;
                        } else {
                            document.getElementById("year").innerHTML = startYear + " - " + todayYear;
                            var yearsAndDaysTip = 'This site has been running for ' + diffYears + ' years and '
                                + diffDays + ' days';
                            if (language === 'zh-CN') {
                                yearsAndDaysTip = '本站已运行 ' + diffYears + ' 年 ' + diffDays + ' 天';
                            } else if (language === 'zh-HK') {
                                yearsAndDaysTip = '本站已運行 ' + diffYears + ' 年 ' + diffDays + ' 天';
                            }
                            document.getElementById("sitetime").innerHTML = yearsAndDaysTip;
                        }
                    }

                    calcSiteTime();
                </script>
            
            <br>
            
                <span id="icp"><img src="/medias/icp.png"
                                    style="vertical-align: text-bottom;"/>
                <a href="https://beian.miit.gov.cn" target="_blank">陕ICP备2021014294号-1</a>
            </span>
            
        </div>
        <div class="col s12 m4 l4 social-link social-statis">
    <a href="https://github.com/jackwang0108" class="tooltipped" target="_blank" data-tooltip="访问我的GitHub" data-position="top" data-delay="50">
        <i class="fab fa-github"></i>
    </a>



    <a href="mailto:2232123545@qq.com" class="tooltipped" target="_blank" data-tooltip="邮件联系我" data-position="top" data-delay="50">
        <i class="fas fa-envelope-open"></i>
    </a>







    <a href="tencent://AddContact/?fromId=50&fromSubId=1&subcmd=all&uin=2232123545" class="tooltipped" target="_blank" data-tooltip="QQ联系我: 2232123545" data-position="top" data-delay="50">
        <i class="fab fa-qq"></i>
    </a>







</div>
    </div>
</footer>

<div class="progress-bar"></div>


    <!-- 搜索遮罩框 -->
<div id="searchModal" class="modal">
    <div class="modal-content">
        <div class="search-header">
            <span class="title"><i class="fas fa-search"></i>&nbsp;&nbsp;搜索</span>
            <input type="search" id="searchInput" name="s" placeholder="请输入搜索的关键字"
                   class="search-input">
        </div>
        <div id="searchResult"></div>
    </div>
</div>

<script type="text/javascript">
$(function () {
    var searchFunc = function (path, search_id, content_id) {
        'use strict';
        $.ajax({
            url: path,
            dataType: "xml",
            success: function (xmlResponse) {
                // get the contents from search data
                var datas = $("entry", xmlResponse).map(function () {
                    return {
                        title: $("title", this).text(),
                        content: $("content", this).text(),
                        url: $("url", this).text()
                    };
                }).get();
                var $input = document.getElementById(search_id);
                var $resultContent = document.getElementById(content_id);
                $input.addEventListener('input', function () {
                    var str = '<ul class=\"search-result-list\">';
                    var keywords = this.value.trim().toLowerCase().split(/[\s\-]+/);
                    $resultContent.innerHTML = "";
                    if (this.value.trim().length <= 0) {
                        return;
                    }
                    // perform local searching
                    datas.forEach(function (data) {
                        var isMatch = true;
                        var data_title = data.title.trim().toLowerCase();
                        var data_content = data.content.trim().replace(/<[^>]+>/g, "").toLowerCase();
                        var data_url = data.url;
                        data_url = data_url.indexOf('/') === 0 ? data.url : '/' + data_url;
                        var index_title = -1;
                        var index_content = -1;
                        var first_occur = -1;
                        // only match artiles with not empty titles and contents
                        if (data_title !== '' && data_content !== '') {
                            keywords.forEach(function (keyword, i) {
                                index_title = data_title.indexOf(keyword);
                                index_content = data_content.indexOf(keyword);
                                if (index_title < 0 && index_content < 0) {
                                    isMatch = false;
                                } else {
                                    if (index_content < 0) {
                                        index_content = 0;
                                    }
                                    if (i === 0) {
                                        first_occur = index_content;
                                    }
                                }
                            });
                        }
                        // show search results
                        if (isMatch) {
                            str += "<li><a href='" + data_url + "' class='search-result-title'>" + data_title + "</a>";
                            var content = data.content.trim().replace(/<[^>]+>/g, "");
                            if (first_occur >= 0) {
                                // cut out 100 characters
                                var start = first_occur - 20;
                                var end = first_occur + 80;
                                if (start < 0) {
                                    start = 0;
                                }
                                if (start === 0) {
                                    end = 100;
                                }
                                if (end > content.length) {
                                    end = content.length;
                                }
                                var match_content = content.substr(start, end);
                                // highlight all keywords
                                keywords.forEach(function (keyword) {
                                    var regS = new RegExp(keyword, "gi");
                                    match_content = match_content.replace(regS, "<em class=\"search-keyword\">" + keyword + "</em>");
                                });

                                str += "<p class=\"search-result\">" + match_content + "...</p>"
                            }
                            str += "</li>";
                        }
                    });
                    str += "</ul>";
                    $resultContent.innerHTML = str;
                });
            }
        });
    };

    searchFunc('/search.xml', 'searchInput', 'searchResult');
});
</script>

    <!-- 回到顶部按钮 -->
<div id="backTop" class="top-scroll">
    <a class="btn-floating btn-large waves-effect waves-light" href="#!">
        <i class="fas fa-arrow-up"></i>
    </a>
</div>


    <script src="/libs/materialize/materialize.min.js"></script>
    <script src="/libs/masonry/masonry.pkgd.min.js"></script>
    <script src="/libs/aos/aos.js"></script>
    <script src="/libs/scrollprogress/scrollProgress.min.js"></script>
    <script src="/libs/lightGallery/js/lightgallery-all.min.js"></script>
    <script src="/js/matery.js"></script>

    

    
        
        <script type="text/javascript">
            // 只在桌面版网页启用特效
            var windowWidth = $(window).width();
            if (windowWidth > 768) {
                document.write('<script type="text/javascript" src="/libs/others/sakura.js"><\/script>');
            }
        </script>
    

    <!-- 雪花特效 -->
    

    <!-- 鼠标星星特效 -->
    

     
        <script src="https://ssl.captcha.qq.com/TCaptcha.js"></script>
        <script src="/libs/others/TencentCaptcha.js"></script>
        <button id="TencentCaptcha" data-appid="xxxxxxxxxx" data-cbfn="callback" type="button" hidden></button>
    

    <!-- Baidu Analytics -->

    <!-- Baidu Push -->

<script>
    (function () {
        var bp = document.createElement('script');
        var curProtocol = window.location.protocol.split(':')[0];
        if (curProtocol === 'https') {
            bp.src = 'https://zz.bdstatic.com/linksubmit/push.js';
        } else {
            bp.src = 'http://push.zhanzhang.baidu.com/push.js';
        }
        var s = document.getElementsByTagName("script")[0];
        s.parentNode.insertBefore(bp, s);
    })();
</script>

    
    <script src="/libs/others/clicklove.js" async="async"></script>
    
    
    <script async src="/libs/others/busuanzi.pure.mini.js"></script>
    

    

    

    <!--腾讯兔小巢-->
    
    

    

    

    
    <script src="/libs/instantpage/instantpage.js" type="module"></script>
    

</body>

</html>
